UNIVERSIDADE DE SANTIAGO DE COMPOSTELA
Depa amen o de Elec ónica y Compu ación
Cen o de In es igación en Tecnoloxías da In o mación (CiTIUS)
Tesis Doc o al
Spec al-spa ial classi ica ion o n-dimensional images in eal- ime
based on segmen a ion and ma hema ical mo phology on GPUs
P esen ada po :
Pablo Quesada Ba iuso
Di igida po :
D a. Do a Blanco He as
D . F ancisco A güello Ped ei a
Julio de 2015
D a. Do a Blanco He as, P o eso a Ti ula de Uni e sidad del Á ea de A qui ec u a de
Compu ado es de la Uni e sidad de San iago de Compos ela
D . F ancisco A güello Ped ei a, P o eso Ti ula de Uni e sidad del Á ea de A qui ec u a de
Compu ado es de la Uni e sidad de San iago de Compos ela
HACEN CONSTAR:
Que la memo ia i ulada Spec al-spa ial classi ica ion o n-dimensional images in eal- ime based
on segmen a ion and ma hema ical mo phology on GPUs ha sido ealizada po D. Pablo Quesada
Ba iuso bajo nues a di ección en el Depa amen o de Elec ónica y Compu ación y en el Cen o Sin-
gula de In es igación en Tecnoloxías da In o mación de la Uni e sidad de San iago de Compos ela, y
cons i uye la Tesis que p esen a pa a ob a al í ulo de Doc o .
Y au o izan la p esen ación de la esis indicada, conside ando que eune los equisi os exigidos en el
a ículo 34 de la egulación de Es udios de Doc o ado, y que como di ec o es de la misma no incu en
en las causas de abs ención es ablecidas en la ley 30/1992.
San iago de Compos ela, Julio de 2015
Do a Blanco He as
Di ec o a de la esis
F ancisco A güello Ped ei a
Di ec o de la esis
To I. L. V.
My s a , my pe ec silence.
“I you spend oo much ime hinking abou a
hing, you’ll ne e ge i done. Make a leas one
de ini i e mo e daily owa d you goal.“
B uce Lee.
“Wi h g ea powe he e mus also come – g ea
esponsibili y!.“
Amazing Fan asy #15 – The i s Spide -Man s o y.
Acknowledgmen s
I would like o exp ess my g a i ude o all he people who ha e suppo ed me du ing my
hesis. Special hanks goes o my hesis ad iso s, Do a Blanco He as and F ancisco A güello
Ped ei a, o hei guidance, suppo and pa ience. Thei con inuous con idence in my wo k
and hei mo i a ion ha e been decisi e in he comple ion o his disse a ion.
I would also like o acknowledge he Depa men o Elec onics and Compu e Science,
specially o he Compu e A chi ec u e G oup, and o he Cen o Singula de In es igación
en Tecnoloxías da In o mación (CiTIUS) a he Uni e si y o San iago de Compos ela, o
p o iding he necessa y esou ces and echnical suppo equi ed by his p ojec .
My g a i ude also goes o P o . Jon A li Benedik sson, Uni e si y o Iceland, and P o .
Lo enzo B uzzone, Uni e si y o T en o, o hei ad ise and kind suppo du ing my s age in
hei esea ch g oups.
My deepes hanks o my amily and close iends o hei ne e ending pa ience and
encou agemen du ing ha d momen s h ough all hese yea s.
Finally, I am also hank ul o he ollowing ins i u ions o he unding p o ided o his
wo k: Minis y o Science and Inno a ion, Go e nmen o Spain, co ounded by he FEDER
unds o Eu opean Union, unde con ac TIN 2010-1754, and by Xun a de Galicia unde
con ac s 08TIC001206PR and 2010/28.
Julio de 2015
x i Lis o Ac onyms
DWT disc e e wa ele ans o m
EAP Ex ended A ibu e P o ile
EM Expec a ion Maximiza ion
EMAP Ex ended Mul i-A ibu e P o ile
EMP Ex ended Mo phological P o ile
FE Fea u e Ex ac ion
FPGA Field P og ammable Ga e A ay
FS Fea u e Selec ion
GPU G aphics P ocessing Uni
HPC High Pe o mance Compu ing
HSEG Hie a chical Image Segmen a ion
ICA Independen Componen Analysis
MM Ma hema ical Mo phology
MNF Minimum Noise F ac ion
MP Mo phological P o ile
MV Majo i y Vo e
nDn-dimensional
NPP NVIDIA Pe o mance P imi i es
NWFE Non-pa ame ic Weigh ed Fea u e Ex ac ion
OA O e all Accu acy
OAO One-Agains -One
PC P incipal Componen
x ii
PCA P incipal Componen Analysis
PR pos - egula iza ion
RBF Radial Basis Func ion
RCMG Robus Colo Mo phological G adien
ROSIS-03 Re lec i e Op ics Sys em Imaging Spec ome e
SE s uc u ing elemen
SM S eaming Mul ip ocesso
SP Scala P ocesso
SVM Suppo Vec o Machine
WT Wa ele T ans o m
Resumen
El p opósi o de es a esis es desa olla esquemas e icien es pa a clasi ica imágenes n-dimen-
sionales usando écnicas de segmen ación y mo ología ma emá ica (MM), y máquinas de
sopo e ec o ial (SVM) como clasi icado es. Po esquemas e icien es en endemos aquellos
que p oducen buenos esul ados en é minos de p ecisión así como los que se pueden ejecu a
en iempo eal en a qui ec u as de bajo cos e. En la búsqueda de es os esquemas es ablecemos
pues un doble obje i o; uno, en e e encia a la p ecisión y, o o, al iempo de ejecución. El
p ime de ellos se log a median e el diseño de nue os esquemas, mien as que, el segundo, se
consigue median e el desa ollo de écnicas que pe mi en su ejecución e icien e en ha dwa e
disponible en o denado es pe sonales, como las CPUs mul i-hilo y las unidades de p ocesado
g á ico (GPU, G aphics P ocessing Uni , en inglés). Las imágenes n-dimensionales engloban
an o a las imágenes de dos y es dimensiones, ejemplo de ello son las u ilizadas en el ámbi o
médico, como ambién a las imágenes desde diez has a cien os de dimensiones, como las imá-
genes mul i- e hipe espec ales adqui idas en elede ección. En el análisis de imágenes mul i-
e hipe espec ales, un pixel se ep esen a como un ec o de alo es espec ales o ca ac e-
ís icas al que llamamos pixel ec o . Las imágenes hipe espec ales se adquie en median e
senso es óp icos que cap u an di e en es longi udes de onda a la ez, desde el espec o isible
has a ce ca del in a ojo. Es a colección de da os se puede e como un cubo hipe espec al
o mado po a ias bandas espec ales. [66].
El p ime senso mul iespec al a bo do de un sa éli e, el Landsa -1 en 1972, e a capaz
de ecoge 4 bandas espec ales con una esolución espacial de 80 me os po píxel [95]. Los
cien os de bandas hipe espec ales llega on en no iemb e del año 2000 con el espec óme o
Hype ion [123]. Desde en onces, la elede ección ha sido un á ea de in es igación muy ac i a
pa a el mapeo de mine ales [92], la iden i icación de zonas u banas; po ejemplo, pa a la
de ección de cambios u banís icos [107], y pa a el análisis en la deg adación de los bosques,
xx Resumen
en e o as [66, 128]. En es e abajo se han u ilizado imágenes hipe espec ales cap u adas
po el Ai bo ne Visible-in a ed Imaging Spec ome e (AVIRIS) [71] y el Re lec i e Op ics
Sys em Imaging Spec ome e (ROSIS-03) [113]. Es os dos senso es hipe espec ales cub en
una gama de 0,4a0,86 µm (ROSIS-03) y de 0,4a2,4µm (AVIRIS) u ilizando 115 y 224
canales espec ales, espec i amen e, con una esolución espacial que a ía en e 1 y 20 m /
pixel.
Las ca ac e ís icas especiales de las imágenes hipe espec ales, que p opo cionan in o ma-
ción de allada pa a cada píxel, pe mi en dis ingui en e ma e iales ísicos y obje os incluso a
ni el de un píxel. La al a dimensionalidad de los da os p esen a nue os desa íos en écnicas
como desmezclado de in o mación espec al (unmixing) [89, 23, 24], de ección de obje i os
y anomalías [107, 14], ex acción de ca ac e ís icas [14], o ca ac e ización y clasi icación de
la supe icie e es e [96, 128]. Es e úl imo ha sido un campo muy in es igado en las úl i-
mas décadas. En e los di e en es e os, es a esis se ocupa de la clasi icación de imágenes
n-dimensionales.
La clasi icación consis e en ag upa y e ique a elemen os que engan en común una o más
p opiedades o ca ac e ís icas. El éxi o de una clasi icación depende de la habilidad pa a ca e-
go iza y/o disc ima cosas, así como en el conjun o del ca ac e ís icas usadas pa a al in; po
lo an o, usa las ca ac e ís icas más ele an es es un equisi o imp escindible. En el análisis
de imágenes, la clasi icación es un mé odo usado con egula idad pa a ex ae in o mación en
medicina, igilancia, manu ac u ación y en elede ección [128, 146]. Las ca ac e ís icas que
in e ienen en el p oceso de ap endizaje pa a clasi ica un píxel en una imagen es án p inci-
palmen e elacionadas con la in ensidad y el colo de dicho pixel, po ejemplo, los canales
ojo, e de y azul en una imagen en RGB.
En las imágenes hipe espec ales enemos muchas más ca ac e ís icas que podemos usa
en es e p oceso; sin emba go, dicho conjun o de da os espec ales esul a en ocasiones e-
dundan e, po lo que se usan écnicas pa a ex acción de ca ac e ís icas como el análisis en
componen es p incipales (PCA) con el obje i o de educi la dimensionalidad y ex ae las
p incipales ca ac e ís icas que ep esen an a es as imágenes [146]. Hemos in es igado di-
e en es écnicas pa a ex ae ca ac e ís icas como análisis de componen es independien es
(ICA), acción mínima de uido (Minimum Noise F ac ion en inglés), DAFE (Disc iminan
Analysis Fea u e Ex ac ion), DBFE (Decision Bounda y Fea u e Ex ac ion) y NWFE (Non-
pa ame ic Weigh ed Fea u e Ex ac ion).
xxi
Pa a saca el máximo p o echo a las imágenes n-dimensionales, se han p opues o un g an
núme o de mé odos de clasi icación [72, 55, 146], como máxima e osimili ud, edes neu-
onales, á boles de decisión y mé odos basados en máquinas de sopo e ec o ial (Suppo
Vec o Machines (SVM) en inglés). En un es udio exhaus i o de clasi icado es p esen ado
en [60] los au o es concluye on que las SVMs es aban en e los mejo es mé odos. En el cam-
po de elede ección, SVM ha demos ado que puede ob ene buenos esul ados en clasi icación
de imágenes hipe espec ales, incluso cuando el núme o de mues as de en enamien o es pe-
queño [72, 55]; po es os mo i os, hemos usado SVM como mé odo de clasi icación en es e
abajo.
Independien emen e de la obus ez de las SVMs, es os mé odos p ocesan cada pixel de
la imagen de o ma independien e conside ando únicamen e la in o mación espec al; sin
emba go, se ha e i icado que la in o mación espacial que se puede ex ae de una imagen
hipe espec al mejo a la p ecisión de la clasi icación cuando se inco po a den o de un esque-
ma espec al-espacial [164, 15, 54, 154, 155, 41, 19, 29, 56, 57]. Po lo an o, los esquemas
de clasi icación de imágenes hipe espec ales han cambiado de clasi icado es a ni el de pixel
hacia esquemas de clasi icación espec al-espacial. Un es udio de es os a ances se ecoge en
[58, 24, 65]. En pa icula , en es a esis es amos in e esados en los esquemas que ex aen la
in o mación espacial en base a écnicas de segmen ación y pe iles mo ológicos.
Las écnicas de segmen ación han sido in es igadas en elede ección pa a ex ae in o ma-
ción de las imágenes hipe espec ales e inco po a la en los esquemas de clasi icación [117,
12, 154, 155, 157, 132, 160]. Al usa las egiones c eadas median e segmen ación enemos
en cuen a las es uc u as espaciales que pueden es a p esen es en la imagen, po ejemplo,
las écnicas de segmen ación usadas en [12] es án basadas en mé odos de conjun o de ni el
(le el-se en inglés). Algo i mos basados en clus e ing (c eación de pa iciones en la ima-
gen ag upando píxeles simila es) se han usado en [154], y écnicas basadas en e olución de
au óma as celula es ue on diseñadas y aplicadas en [132] pa a segmen ación de imágenes
hipe espec ales sin educi la dimensionalidad de los da os. La ans o mada wa e shed se ha
aplicado en los esquemas espec ales-espaciales p esen ados en [117, 155, 156, 158, 78]. Til-
on [160] p opuso un algo i mo de segmen ación je á quica denomidado HSEG (hie a chical
segmen a ion) que combina dos mé odos de segmen ación pa a uni egiones y mejo a los
esul ados. En e odas las écnicas, la ans o mada wa e shed [168] ha despe ado mayo in-
e és en los esquemas de clasi icación basados en la segmen ación, a pesa de que no se puede
aplica di ec amen e a una imagen n-dimensional. El en oque más común pa a la aplicación
xxii Resumen
de es a écnica en imágenes hipe espec ales consis e en educi el núme o de dimensiones
espec ales a uno, po ejemplo, median e educción de ca ac e ís icas (PCA) o algo i mos de
g adien e ec o ial (RCMG) [155]. En es a esis hemos desa ollado un esquema de clasi i-
cación basado en segmen ación (CA–WSHED–MV) [137] usando au óma as celula es pa a
calcula de o ma e icien e la ans o mada wa e shed (CA–Wa e shed). Es e algo i mo, CA–
Wa e shed [139, 135, 138], es ap opiado pa a a qui ec u as mul i-hilo como las CPUs y las
unidades de p ocesado g á ico (GPUs), ya que el au óma a se puede di idi en bloques que
se ac ualizan de o ma independien e.
La mo ología ma emá ica (MM) se de ine como la eo ía pa a el análisis de es uc u as
espaciales [152] y se ha usado con éxi o en clasi icación de imágenes n-dimensionales en el
campo de la elede ección, a a és de pe iles mo ológicos (Mo phological P o iles (MP)
en inglés) [124] y pe iles mo ológicos basados en a ibu os (a ibu e p o iles) [41] con los
que es posible analiza di e en es ipos de es uc u as. Los pe iles mo ológicos eliminan ob-
je os que no encajan den o de la es uc u a de un elemen o de análisis, llamado s uc u ing
elemen (SE). Aplicando sucesi amen e ope aciones mo ológicas con elemen os es uc u a-
les de dis in o amaño se c ea una ep esen ación de la imagen con a ios ni eles de de alle.
El uso en imágenes n-dimensionales es posible aplicando los pe iles a cada banda (o a
un conjun o ep esen a i o) a a és de pe iles mo ológicos ex endidos (EMPs) [121, 15],
y de pe iles basados en a ibu os ex endidos (EAPs) [41]. Los EAPs se pueden c ea con
di e en es a ibu os, po ejemplo, el á ea o la des iación es anda d del colo de una egión,
ex ayendo más in o mación espacial y dando luga a los pe iles mo ológicos basados en
mul i-a ibu os (EMAPs) [42]. En gene al, los esquemas de clasi icación basados en MM
usando pe iles ex endidos (EMP, EAP, EMAP) han demos ado se más e icien es en é minos
de p ecisión que los esquemas basados en segmen ación [58, 65], a cambio de inc emen a el
cos e compu acional. En es a esis hemos desa ollado un esquema de clasi icación espec al-
espacial basado en EMP (WT–EMP), eniendo en cuen a su pos e io ejecución en ha dwa e
de bajo cos e pa a p ocesamien o en iempo eal. Es e esquema c ea un EMP a pa i de un
conjun o ep esen a i o de los da os y los conca ena con la in o mación espec al c eando un
nue o conjun o nue o de ca ac e ís icas pa a cada pixel.
Independien emen e de las écnicas u ilizadas en los esquemas de clasi icación, allos en
la calib ación de los senso es o enómenos a mos é icos pueden a ec a a la calidad de los
da os [146]. La consecuencia más común es la p esencia de uido en la imagen. Po lo an o,
no malmen e se equie e un p ep ocesado de los da os pa a educción de uido [164, 166]
xxiii
o co ección de dispe sión [140]. La ans o mada wa ele es una he amien a ma emá ica
pa a p ocesamien o de señales que se ha aplicado en elede ección pa a il ado de uido,
así como o os p ep ocesados de la imagen como comp esión de da os [61] y educción de
ca ac e ís icas [86]. En el esquema WT–EMP p opues o en es a esis, usamos la ans o mada
wa ele pa a ex acción de ca ac e ís icas an es de c ea el pe il mo ológico ex endido, y
ambién pa a elimina uido en cada banda espec al de la imagen o iginal.
A pesa de que exis en una g an a iedad de esquemas de clasi icación espec al-espacial,
la mayo ía esul an compu acionalmen e poco e icien es en é minos de iempos de ejecución
debido al g an olumen de da os al que deben hace en e. Po lo an o, pa a el uso de es os
esquemas en aplicaciones en iempo eal necesi amos implemen aciones e icien es en las a -
qui ec u as usadas pa a su ejecución. Es o es de especial in e és en aplicaciones con iempo de
espues a c í ico como moni o ización de desas es na u ales o de ección de obje i os a bo do
pa a sal amen o ma í imo, donde la oma de decisiones se hace en iempo eal [129, 77, 18].
Además, como las imágenes n-dimensionales han es ado más disponibles en los úl imos años
debido p incipalmen e a la educción en amaño y cos e de los senso es espec ales, el nú-
me o de aplicaciones a mediana y pequeña escala como es el con ol de la calidad en los
alimen os [30], la de ección de alsi icaciones en ob as de a e [100], el diagnós ico de en e -
medades [30, 102] y medicina o ense [50], ambién se ha is o inc emen ado. La necesidad
de una compu ación e icien e en a qui ec u as de bajo cos e es á aumen ando a medida que
inco po amos es a ecnología en aplicaciones de uso dia io. En es a esis nos hemos cen ado
en diseña y desa olla esquemas de clasi icación e icien es aplicados al campo de la elede-
ección pa a p ocesa imágenes de la supe icie e es e en iempo eal.
El campo de la compu ación de al as p es aciones aplicado a la elede ección aba ca desde
g andes in aes uc u as de se ido es [49, 75, 130] has a ha dwa e de bajo cos e como las
FPGAs (Field P og ammable Ga e A ays, en inglés) [129, 126, 67], pasando po CPUs mul i-
hilo y las GPUs [126, 127, 67, 36, 20, 137]. Mucha de la in es igación en es e á ea se ha
cen ado en el campo de desmezclado de in o mación espec al [129, 67] y en la de ección de
obje i os [77, 18]. El ha dwa e más idóneo depende p incipalmen e de la aplicación inal, el
p esupues o y el espacio disponible pa a ins ala dicho ha dwa e. En el caso de esquemas de
clasi icación espec al-espacial muy pocos se han adap ado pa a la GPU [20, 137] o han sido
especialmen e diseñados desde el p incipio pa a al in.
Dadas la complejidad de los sis emas de clasi icación espec al-espacial y la g an can idad
de da os disponibles en las imágenes hipe espec ales, nos plan eamos la siguien e p egun a
xxi Resumen
en es a esis:
¿Es posible diseña esquemas de clasi icación espec al-espacial que p oduz-
can buenos esul ados en é minos de p ecisión, y que se puedan ejecu a en
iempo eal u ilizando in aes uc u as de compu ación de bajo cos e pa a el
p ocesamien o a bo do de da os hipe espec ales?.
El éxi o de un esquema e icien e eque i á de un es udio a ondo pa a encon a écnicas
que mejo en la p ecisión de la clasi icación adap adas al modelo de compu ación de es e
ha dwa e de bajo cos e, como una GPU.
Las con ibuciones p incipales de esa esis son:
1. Análisis de esquemas de clasi icación espec al-espacial basados en la segmen a-
ción y pe iles mo ológicos. En pa icula , nos hemos cen ado en dis in as o mas
de inco po a la in o mación espacial en los sis emas de clasi icación hipe espec ales
basados en SVM. Dedicamos especial a ención a écnicas pa a la ex acción de ca ac e-
ís icas, así como al p ocesamien o espacial basado en mo ología ma emá ica, écnicas
de segmen ación como la ans o mada wa e shed, y écnicas de usión de da os pa a
combina la in o mación espec al y espacial.
2. P opues a de esquemas de clasi icación espec al-espacial. Hemos p opues o los si-
guien es esquemas:
– CA-WSHED–MV [137, 136] es un esquema basado en segmen ación, SVM y
usión de da os ía o ación mayo i a ia. Es e esquema es á basado en el ame-
wo k de clasi icación espec al-espacial p opues o po Ta abalka [156, 155]. El
esquema consis e en calcula un g adien e ec o ial (RCMG) que educe la di-
mensionalidad de la imagen a una sola banda, la cual es segmen ada usando una
ans o mada wa e shed basada en au óma as celula es. La clasi icación se lle a a
cabo median e SVM. Po úl imo, las egiones segmen adas se combinan con los
esul ados de clasi icación usando una écnica de o ación. La no edad de es e
esquema es que el algo i mo de wa e shed, basado en au óma as celula es, no ge-
ne a líneas de segmen ación las cuales no es án asignadas a ninguna egión y, po
lo an o, no necesi a un p ocesamien o adicional pa a inclui dichas líneas en el
esquema. Además, es e algo i mo sigue un modelo de compu ación en el cual las
xx
celdas del au óma a se pueden di idi en g upos y asigna se a di e en es unidades
de compu ación, donde se pueden ac ualiza de o ma asínc ona.
– WT–EMP [133] es un esquema basado en wa ele s, mo ología ma emá ica y
SVM. Fue diseñado eniendo en cuen a su pos e io ejecución en GPU. La ans-
o mada wa ele se usa 1) pa a ex ae in o mación espec al usando il os 9/7,
y 2) pa a educción de uido u ilizando un conjun o de es il os [148]. La mo -
ología ma emá ica se usa pa a c ea un pe il mo ológico ex endido a pa i de
las ca ac e ís icas ex aídas po wa ele s. Es e nue o esquema de clasi icación
espec al-espacial mejo a los esul ados en é minos de clasi icación en compa a-
ción con o os basados en segmen ación y MM.
3. Desa ollo de écnicas y es a egias pa a compu ación e icien e en GPU. Hemos
aplicado di e en es es a egias, y en pa icula , hemos p opues o una es a egia basada
en compu ación asínc ona (block–asynch onous) con la que es posible ejecu a au óma-
as celula es en GPU de o ma más e icien e. Es a es a egia educe el núme o de pun os
globales de sinc onización y explo a de o ma e icien e la je a quía de memo ia de es a
a qui ec u a; además, esul a adecuada pa a a qui ec u as mul i-hilo y se ha adap ado
pa a su uso an o en imágenes 2D como en olúmenes en 3D. En pa icula , la hemos
aplicado a:
– CA–Wa e shed: és e es el au óma a celula asínc ono pa a calcula la ans o -
mada wa e shed en GPU [139, 135, 138]. El compo amien o asínc ono de es a
p opues a in oduce i egula idades en los bo des en e egiones que hemos solu-
cionado co igiendo la elocidad de p opagación en e bloques, usando una écni-
ca denominada wa e on [112].
– Ope aciones mo ológicas de ape u a y cie e po econs ucción basados en el
mismo p incipio de compu ación asínc ona en GPU [134]. Es as écnicas se usan
pa a c ea los pe iles mo ológicos empleados en el esquema WT-EMP.
– Fil ado basado en a ibu os. Se a a de una nue a p opues a pa a el il ado (ape -
u a y cie e) de imágenes en escala de g ises en GPU y que además, se puede
ex ende a di e en es a ibu os. Es e ipo de il ado se aplica en esquemas de cla-
si icación basados en a ibu os ex endidos (EAPs) y mul i-a ibu os (EMAPs).
4. Implemen ación e icien e de esquemas de clasi icación espec al-espacial en CPUs
mul i-hilo y GPUs, usando OpenMP y CUDa, espec i amen e.
4Chap e 1. Thesis o e iew
o Mo phological P o iles (MPs) [124] and A ibu e P o iles (APs) [41], which a e used o
model di e en kinds o spa ial s uc u es (objec s). The p o iles keep objec s in he image i a
s uc u ing elemen o a ibu e i s wi hin he objec , o he wise hey a e emo ed. Th ough he
sequen ial applica ion o mo phological ope a ions and inc easing he size o he s uc u ing
elemen (o il e ), he MP and AP c ea e a mul ile el cha ac e iza ion o he image. The
ex ension o n-dimensional images is possible by applying he p o ile o each band (o o a
ep esen a i e subse ) h ough he Ex ended Mo phological P o ile (EMP) [121, 15] and he
Ex ended A ibu e P o ile (EAP) [41], espec i ely. The la e can be u he ex ended wi h
di e en a ibu e il e s, (e.g. he a ea and s anda d de ia ion o pixel colo s wi hin a egion),
ex ac ing mo e spa ial in o ma ion om he image, c ea ing an Ex ended Mul i-A ibu e
P o ile (EMAP) [42]. In gene al, MM-based classi ica ion schemes using ex ended p o iles
ha e shown o be mo e e icien han segmen a ion-based app oaches in e ms o classi ica ion
accu acy [58, 65], a he expense o inc easing he compu a ional cos . In his hesis we
ha e de eloped a scheme based on Ex ended Mo phological P o iles (WT–EMP) and aking
in o accoun i s subsequen p ojec ion on low-cos compu ing in as uc u es o eal- ime
p ocessing. The scheme c ea es he EMP om a ep esen a i e subse o he hype spec al
bands ha is combined wi h he spec al da a in a new ec o o ea u es.
Rega dless o he echniques used in emo e sensing, undesi able a i ac s such as im-
p ope calib a ion o he senso o a mosphe ic phenomena may a ec da a quali y [146]. The
mos common consequence o hese a i ac s is he p esence o noise in he image. The e o e,
a p ep ocessing s ep, such as denoising [164, 166] o sca e co ec ion [140], is usually e-
qui ed be o e classi ying he images. Wa ele s a e ma hema ical ools o signal p ocessing
and ha e been in es iga ed in emo e sensing o il e ing he noise in oduced in he acquisi-
ion o he image, as well as addi ional p ep ocessing like da a comp ession [61] and ea u e
ex ac ion [86]. In he WT–EMP scheme p oposed in his hesis, wa ele s a e used o ea u e
ex ac ion o c ea e he EMP, and also o denoising o e each band o he o iginal hype spec-
al image.
Al hough he e a e many spec al-spa ial classi ica ion schemes, mos a e compu a ion-
ally ine icien in e ms o execu ion ime, as hey ha e o deal wi h a high numbe o ea u es
esul ing in la ge execu ion imes. The e o e, he compu a ion o hese schemes o eal- ime
applica ions equi es hei e icien implemen a ion on he adequa e compu ing a chi ec u e.
This is pa icula ly ue in ime-c i ical applica ions in emo e sensing, such as na u al disas-
e s moni o ing and on-boa d a ge de ec ion o ma i ime escue whe e decisions a e made
1.1. Main con ibu ions 5
in eal ime [129, 77, 18]. In addi ion, as he hype spec al images ha e been widely a ailable
in ecen yea s owing o he educ ion in he size and cos o he senso s, he numbe o ap-
plica ions a lab scale, such as ood quali y con ol [30], a o ge y de ec ion [100], disease
diagnosis [30, 102] and o ensics [50], has also inc eased. The need o e icien compu a ion
on low-cos compu ing in as uc u es is inc easing in line wi h he inco po a ion o echnol-
ogy in o e e yday applica ions. This hesis ocuses on de eloping e icien spec al-spa ial
schemes o land-co e classi ica ion in emo e sensing imaging o eal- ime applica ions.
The esea ch in High Pe o mance Compu ing (HPC) o emo e sensing applica ions co -
e s a ield anging om in as uc u es o clus e s [49, 75, 130] o Field P og ammable Ga e
A ays (FPGAs) [129, 126, 67] and commodi y ha dwa e such as mul i- h eaded CPUs and
many-co e GPUs [126, 127, 67, 36, 20, 137]. Mos o he esea ch in HPC o emo e sensing
has been done in he ield o spec al unmixing in ol ing endmembe ex ac ion [129, 67],
and also in a ge de ec ion [77, 18]. The mos sui able ha dwa e o HPC depends mainly
on he inal applica ion, he budge and he space a ailable o he compu ing in as uc u es.
The GPU, wi h i s high compu a ional capaci y has no been ye ully exploi ed. In he case o
spec al-spa ial classi ica ion schemes, only a ew ha e been adap ed o GPU [20, 137], and
e en ewe ha e been specially designed o ha pu pose om he ou se .
Gi en he complexi y o he spec al-spa ial classi ica ion schemes, and he high amoun
o da a a ailable in he hype spec al images, we posed he ollowing ques ion in his hesis:
Is i possible o design e icien spec al-spa ial classi ica ion schemes ha p o-
duce good classi ica ion esul s and can be execu ed in eal- ime, using low-cos
compu ing in as uc u es o on-boa d p ocessing o hype spec al in o ma-
ion?
The success o an e icien scheme will equi e a ho ough s udy o ind echniques ha
imp o e he classi ica ion accu acy, while ma ching he compu ing model o he low-cos
compu ing in as uc u es, such as a GPU.
1.1 Main con ibu ions
As a esul o he esea ch conduc ed in his hesis o ind a solu ion o ou main ques ion, he
ollowing con ibu ions o he ield o emo e sensing and HPC ha e been p oduced:
6Chap e 1. Thesis o e iew
1. Analysis o spec al-spa ial classi ica ion schemes based on segmen a ion and mo -
phological p o iles. In pa icula , we ocus on he di e en ways o inco po a ing spa-
ial in o ma ion in o he pixel-wise spec al classi ica ion schemes based on he SVM
classi ie . We de o e special a en ion o ea u e ex ac ion echniques, as well as spa ial
p ocessing by ma hema ical mo phology, segmen a ion echniques based on clus e ing,
such as kmeans and quick-shi , and segmen a ion echniques based on egion g owing
such as he wa e shed ans o m, and da a usion s a egies o combining he spec al
and spa ial in o ma ion. We ha e aken in o accoun he e icien compu a ion on GPU
o he echniques unde s udy.
2. P oposal o spec al-spa ial classi ica ion schemes. The ollowing schemes a e p o-
posed:
– CA-WSHED–MV [137, 136] is a scheme based on segmen a ion, SVM and Ma-
jo i y Vo e. This scheme is based on he spec al-spa ial classi ica ion amewo k
p oposed by Ta abalka e al. [156, 155]. The scheme consis s o he calcula ion
o a Robus Colo Mo phological G adien (RCMG) which educes he dimen-
sionali y o he hype spec al image, ollowed by he calcula ion o a wa e shed
ans o m based on cellula au oma a which p oduces he spa ial esul s. The clas-
si ica ion is ca ied ou by SVM. Finally, he spec al and spa ial esul s a e com-
bined wi h a majo i y o e. The no el y o his scheme is mainly in oduced in
he wa e shed algo i hm based on cellula au oma a used o segmen ing he hy-
pe spec al image. This algo i hm ollows a compu a ional model in which he
g id o cells o he au oma on is pa i ioned in o egula egions ha a e assigned
o di e en blocks o h eads on he GPU ha can be asynch onously upda ed. In
addi ion, his implemen a ion does no c ea e he so-called wa e shed lines, and
hus i is no necessa y o compu e a s anda d ec o median [7] o e e y wa e -
shed egion as in [155].
– WT–EMP [133] is a scheme based on wa ele s, MM and SVM. This scheme was
designed aking in o accoun i s e icien compu a ion in a subsequen GPU exe-
cu ion. The Wa ele T ans o m is used o ea u e ex ac ion and image denoising
using 9/7 wa ele il e s o he o me and a se o h ee il e s o pe ec econ-
s uc ion [148] o he la e . Ma hema ical Mo phology is used o c ea ing he
EMP om he ea u es ex ac ed by wa ele s. This new spec al-spa ial classi i-
1.1. Main con ibu ions 7
ca ion scheme imp o es he classi ica ion esul s in e ms o accu acy in compa -
ison o o he spec al-spa ial schemes based on segmen a ion and Ma hema ical
Mo phology.
3. De elopmen o echniques and s a egies o e icien GPU compu ing. Di e en
s a egies a e applied and, in pa icula , a block–asynch onous s a egy ha maps cel-
lula au oma a on he GPU is p oposed. This s a egy educes he numbe o poin s o
global synch oniza ion allowing e icien exploi a ion o he memo y hie a chy o his
a chi ec u e. The block–asynch onous s a egy is also adequa e o mul ico e a chi ec-
u es, and i has been uned o be used wi h 2D and 3D images. I is applied o:
– CA–Wa e shed: his is an asynch onous cellula au oma on o compu e he wa-
e shed ans o m on GPU [139, 135, 138]. The asynch onous beha io o he
CA–Wa e shed in oduces a i ac s in he bo de o he segmen ed egions ha a e
ixed by co ec ing he da a p opaga ion speed among he blocks using wa e on
echniques [112].
– Opening and closing: an imp o ed algo i hm o opening and closing by econ-
s uc ion on GPU based on he block-asynch onous app oach (BAR) [134]. The
algo i hm is applied o c ea e he Ex ended Mo phological P o ile used in land-
co e spec al-spa ial classi ica ion schemes.
– A ibu e il e ing: a new p oposal o g eyscale a ibu e opening and closing on
GPU. This p oposal is he i s a emp o compu e his il e on g eyscale images
on GPU and can be ex ended o o he a ibu es. The p oposal can be applied o
c ea e an Ex ended A ibu e P o ile o land-co e spec al-spa ial classi ica ion
schemes.
4. E icien implemen a ion o spec al-spa ial classi ica ion schemes on mul i- h eaded
CPUs and many-co e GPUs by using OpenMP and CUDA, espec i ely.
– CA–WSHED-GPU [136, 137] is an e icien p ojec ion on GPU o he i s p o-
posed scheme (CA-WSHED-MV). Di e en hype spec al da a pa i ioning s a e-
gies and h ead block a angemen s a e s udied in o de o e ec i ely exploi he
memo y and compu ing capabili ies o his a chi ec u e. The spec al pa i ioning
is used o compu e he RCMG. The wa e shed ans o m is based on he asyn-
ch onous cellula au oma on (CA-Wa e shed) ha e icien ly exploi s he GPU
8Chap e 1. Thesis o e iew
a chi ec u e, and he majo i y o e is done by a omic ope a ions o a oid memo y
ace condi ions.
– WT–EMP–GPU [134] is a GPU implemen a ion o he WT–EMP scheme ha
achie es eal- ime in commodi y ha dwa e. We adap ed he ea u e ex ac ion by
wa ele s compu ing housands o pixel ec o s in pa allel. A new implemen a ion
o wo dimensional wa ele ans o ms was equi ed in o de o manage he h ee
il e s used in he denoising s ep. Finally, we used he block–asynch onous s a -
egy o mo phological econs uc ion o compu e he EMP used in he scheme.
Despi e he di e en GPU solu ions o SVM classi ica ion ound in he li e a u e, a new
implemen a ion was de eloped o classi ying mul i-class p oblems on GPU [134], ha
is compa ible wi h he one agains one ained models p oduced by he ac o LIBSVM
lib a y [35].
1.2 Publica ions
1.2.1 Book Chap e s
[137] P. Quesada-Ba iuso, F. A güello, and D. B. He as, “Compu ing e icien ly spec al-
spa ial classi ica ion o hype spec al images on commodi y gpus,” in Recen Ad ances in
Knowledge-based Pa adigms and Applica ions (J. W. Tweedale and L. C. Jain, eds.), ol. 234
o Ad ances in In elligen Sys ems and Compu ing, Ch. 2, pp. 19–42, Sp inge In e na ional
Publishing, 2014.
1.2.2 In e na ional Jou nals
[138] P. Quesada-Ba iuso, D. B. He as, and F. A güello, “E icien 2D and 3D wa e shed on
g aphics p ocessing uni : block-asynch onous app oaches based on cellula au oma a,” Com-
pu e s & Elec ical Enginee ing, ol. 39, no. 8, pp. 2638–2655, 2013.
[78] D. B. He as, F. A güello, and P. Quesada-Ba iuso, “Explo ing ELM-based spa ial-
spec al classi ica ion o hype spec al images,” In e na ional Jou nal o Remo e Sensing, ol.
35, no. 2, pp. 401–423, 2014.
[133] P. Quesada-Ba iuso, F. A güello, and D. B. He as, “Spec al-spa ial classi ica ion o
hype spec al images using wa ele s and ex ended mo phological p o iles,” Selec ed Topics
1.2. Publica ions 9
in Applied Ea h Obse a ions and Remo e Sensing, IEEE Jou nal o , ol. 7, no. 4, pp.
1177–1185, 2014.
[134] P. Quesada-Ba iuso, F. A güello, D. B. He as, and J. A. Benedik sson, “Wa ele -based
classi ica ion o hype spec al images using ex ended mo phological p o iles on g aphics p o-
cessing uni s,” Selec ed Topics in Applied Ea h Obse a ions and Remo e Sensing, IEEE
Jou nal o , ol. PP, no. 99, pp. 1–9, 2015 (published online, p in edi ion pending).
[101] J. López-Fandiño, P. Quesada-Ba iuso, D. B. He as, and F. A güello, “E icien ELM-
based echniques o he classi ica ion o hype spec al emo e sensing images on commodi y
gpus,” Selec ed Topics in Applied Ea h Obse a ions and Remo e Sensing, IEEE Jou nal o ,
ol. PP, no. 99, pp. 1–10, 2015 (published online, p in edi ion pending).
1.2.3 In e na ional Con e ences
[135] P. Quesada-Ba iuso, D. B. He as, and F. A güello, “E icien GPU asynch onous imple-
men a ion o a wa e shed algo i hm based on cellula au oma a,” in Pa allel and Dis ibu ed
P ocessing wi h Applica ions (ISPA), 2012 IEEE 10 h In e na ional Symposium on, pp. 79–
86, 2012.
[136] P. Quesada-Ba iuso, F. A güello, and D. B. He as, “E icien segmen a ion o hype -
spec al images on commodi y GPUs,” in 16 h In e na ional Con e ence on Knowledge-Based
and In elligen In o ma ion & Enginee ing Sys em, ol. 243, pp. 2130–2139, 2012.
1.2.4 Na ional Con e ences
[139] P. Quesada-Ba iuso, J. Lamas-Rod íguez, D. B. He as, and F. A güello, “In luencia
de las mese as en la implemen ación de wa e shed sob e GPUs,” in XXIII Jo nadas de Pa -
alelismo, pp. 249–254, 2012.
[94] J. Lamas-Rod íguez, P. Quesada-Ba iuso, F. A güello, D. B. He as and y M. Bóo,
“P oyección del mé odo de segmen ación del conjun o de ni el en GPU,” in XXIII Jo nadas
de Pa alelismo, pp. 273–278, 2012.
10 Chap e 1. Thesis o e iew
1.3 Thesis o ganiza ion
This hesis is o ganized in six chap e s. Chap e 1 in oduces he objec i es and he main
con ibu ions o his hesis. Chap e 2 p esen s he undamen al concep s in ol ed in his
wo k. Fi s , he main cha ac e is ics o he n-dimensional images a e e iewed. Second, he
echniques used in he p oposed spec al-spa ial classi ica ion schemes a e de ailed. Di e en
ea u e ex ac ion echniques ha ha e been success ully applied in emo e sensing classi i-
ca ion a e desc ibed. The concep s ega ding he spa ial p ocessing o he images, such as
he segmen a ion, ma hema ical mo phology and a ibu e il e ing a e also e iewed in his
chap e . Then, cellula au oma a and he wa ele ans o m a e in oduced, and we e iew he
pixel-wise classi ie s, in pa icula he SVM, he one used in ou schemes. In addi ion, he
OpenMP and Compu e Uni ied De ice A chi ec u e (CUDA) compu ing model, as well as he
ha dwa e esou ces and he pe o mance measu es used in he expe imen s a e in oduced in
his chap e . Finally, he da ase s used in he expe imen s a e desc ibed.
Chap e 3 p esen s ou wo schemes p oposed o e icien n-dimensional image classi i-
ca ion: CA–WSHED–MV and WT–EMP. The gene al amewo k o he spec al-spa ial clas-
si ica ion schemes and he common da a usion s a egies o join he spec al and he spa ial
in o ma ion o such schemes a e p esen ed in his chap e . The esul s he eo a e compa ed on
eal hype spec al images, in e ms o classi ica ion accu acy, wi h he classi ica ion schemes
ound in he li e a u e based on segmen a ion and MM.
Chap e 4 ocuses on he echniques and s a egies applied o he e icien compu a ion o
he p oposed schemes on commodi y ha dwa e such as mul i- h eaded CPUs and many-co e
GPUs. Fi s , we desc ibe he gene al s a egies ela ed o da a pa i ioning, da a mo emen
and da a packing, and highligh he challenges o GPU compu ing. Then, we p esen he
block–asynch onous compu a ion s a egy p oposed in his hesis. This app oach is applied o
compu e an asynch onous CA–Wa e shed, opening and closing by econs uc ion and a ibu e
il e ing by opening and closing. The s a egies o e icien p ojec ion o wa ele s, as well
as mul i-class SVM classi ica ion on GPU a e also desc ibed in his chap e . The echniques
a e independen ly analyzed compa ing he execu ion imes o pa allel mul i- h eaded CPU
implemen a ions using OpenMP.
In chap e 5 we desc ibe he CUDA implemen a ion o he p oposed schemes, named
CA–WSHED–GPU and WT–EMP–GPU, applying he echniques desc ibed in chap e 4. We
also analyze he op imal GPU pa ame e s and he ha dwa e esou ces ha usually limi he
occupancy on his a chi ec u e. The pe o mance is measu ed in e ms o execu ion ime
1.3. Thesis o ganiza ion 11
and speedup on eal hype spec al images o e CPU mul i- h eaded implemen a ions using
commodi y ha dwa e.
Finally, he las chap e ema ks he con ibu ions, p esen s he conclusions and p oposes
u u e esea ch de elopmen s.
CHAPTER 2
FUNDAMENTALS
In his chap e we e iew he undamen al concep s and p esen he echniques used in he
spec al-spa ial classi ica ion schemes p oposed in his hesis. In pa icula , he main cha ac-
e is ics o he n-dimensional images a e e iewed and he concep s ega ding he spa ial p o-
cessing o he images, such as he wa e shed ans o m, cellula au oma a, ec o ial g adien s,
ma hema ical mo phology and wa ele ans o m a e ou lined. We hen go on o desc ibe he
pixel-wise classi ie s and he classi ica ion map p oduced by he same, in pa icula o SVM
ha is he classi ie used in ou scheme. In addi ion, he OpenMP and he CUDA pa allel
p og amming models, as well as he ha dwa e esou ces and he pe o mance measu es a e
in oduced in his chap e . Finally, he da ase s used in he expe imen s a e de ailed.
2.1 n-dimensional images
An-dimensional (nD) image is conside ed a da ase whe e wo dimensions ep esen a spa ial
loca ion [x,y], while he emaining dimensions ep esen phenomena occu ing pe spa ial lo-
ca ion [3]. The e o e, a pixel is ep esen ed as a ec o o alues o ea u es (pixel ec o ). Fo
example, a nD image can be p oduced by op ical senso s which cap u e di e en wa eleng h
esponses (one pe spec al band) in he same line scan. Mul ispec al images usually a e
composed o a ew, usually h ee o en, spec al channels, while hype spec al images ha e
hund eds o spec al bands. These da ase s can be seen as spec al cubes o se e al (hund eds)
images whe e [x,y] a ies ac oss he physical space and [z] a ies ac oss he elec omagne ic
spec um. [66]. A nD image can also be a se o images o he same scene acqui ed by he
20 Chap e 2. Fundamen als
Inpu : inpu da a X
Ou pu : pa i ioning o he da a in kclus e s
1: choose he numbe o kclus e s and ini ialize hei posi ion cj o k ea u e ec o s
2: epea
3: o each ea u e ec o x∈X do
4: assign x o i s closes clus e based on he Euclidean dis ance
5: end o
6: o each clus e Cjdo
7: ecompu e cj o he mean o all he poin s x(j)
ibelonging o ha clus e
8: end o
9: compu e he squa e e o unc ion (2.10)
10: un il s abili y
Figu e 2.2: Pseudocode o k-means clus e ing.
Inpu : inpu image X
Ou pu : hie a chical image segmen a ion
1: label each pixel o Xas a sepa a e egion
2: while he numbe o egions emaining is g ea e han wo do
3: epea
4: calcula e he dissimila i y c i e ion di,jbe ween each spa ially adjacen egion
5: ind he min(di,j)and me ge all pai s o spa ially adjacen egions wi h mee ha alue
6: calcula e he dissimila i y c i e ion si,jbe ween all pai s o non-spa ially adjacen egions
7: me ge all pai s o non-spa ially adjacen egions wi h si,j≤min(di,j)
8: un il s abili y
9: sa e cu en segmen a ion map
10: end while
Figu e 2.3: Pseudocode o HSEG algo i hm.
By analogy, hie a chical segmen a ion can be de ined as a amily o ine o coa se image
pa i ions [153]. Til on p oposed a Hie a chical Image Segmen a ion (HSEG) algo i hm [161]
o exploi ing he in o ma ion con en on he segmen a ion hie a chy. I is a hyb id segmen a-
ion echnique based on hie a chical s ep-wise op imiza ion (HSWO) [13] and da a clus e ing.
The algo i hm al e na ely pe o ms egion g owing me ging spa ially adjacen egions, and
spec al clus e ing me ging spa ially non-adjacen egions.
The HSEG pseudocode shown in Figu e 2.3 is based on he desc ip ion gi en in [161,
173]. The inne loop (lines 3–8) me ges he segmen ed egions o he image. Lines 4 and
2.3. Segmen a ion echniques 21
5 co espond o he egion g owing s ep and lines 6 and 7 cons i u e he spec al clus e ing
pa . The dissimila i y c i e ion is based on he Euclidean dis ance cha ac e ized by he mean
ec o s o he egions. S abili y is eached when he numbe o egions emaining in he
segmen a ion map is lowe han a p ese alue o egions [161]. The ou e loop, lines 2–10
pe o ms he hie a chical segmen a ion o he image.
In clus e ing-based image segmen a ion, he labels in he clus e ing map a e c ea ed om
kdi e en classes; i.e., he e a e only kdis inc alues and he segmen ed egions a e no
connec ed by a unique label. The e o e, a Connec ed Componen Labelling (CCL) algo i hm
is equi ed o e-label he clus e s and p oduce a segmen a ion map [83]. The segmen a ion o
nD images aims a inding dis inc s uc u es in he spec al domain.
2.3.2 Wa e shed ans o m
The wa e shed ans o m is a widely used me hod o non-supe ised image segmen a ion,
especially sui able o low-con as images. The idea behind his me hod comes om geog a-
phy. A g eyscale image can be ep esen ed as a opog aphic elie , whe e he heigh o each
pixel is di ec ly ela ed o i s g ey le el. The di iding lines o he ca chmen basins o p ecip-
i a ion alling o e he egion a e called wa e shed lines [168]. Va ious de ini ions, algo i hms
and implemen a ions can be ound in he li e a u e bu , in p ac ice, hey can be classi ied
in o wo g oups: hose based on he speci ica ion o a ecu si e algo i hm by Vincen and
Soille [168], and hose based on he dis ance unc ions de ined by Meye [111]. An in ui i e
app oach is o imagine he e ain being imme sed in a lake, wi h holes pie ced in local min-
ima [142]. By looding he e ain in o he wa e , ca chmen basins will ill up wi h wa e as
illus a ed in Figu e 2.4. A he poin s whe e wa e coming om di e en basins would mee ,
dams a e buil . The p ocess s ops when he wa e le el eaches he highes peak. The e ain
is pa i ioned in o egions sepa a ed by he wa e shed lines. In Figu e 2.4 he image has wo
minimum g ey alues ep esen ing wo alleys in he e ain.
One o he main ad an ages o he wa e shed ans o m is ha all egions o he image a e
well de ined a he end o he segmen a ion p ocess, e en i he con as o he image is poo .
Hence i has been widely used in image p ocessing, biomedicine and physics. None heless,
he esul s a e o e -segmen ed owing o he la ge numbe o egions de ec ed. This p ob-
lem is o e come by p ep ocessing he image wi h he objec i e o educing he numbe o
egions, o example by a ma ked-con olled wa e shed ans o m ha p eselec s he egions
o in e es [22].
22 Chap e 2. Fundamen als
Figu e 2.4: Flooding p ocess in a one dimensional image wi h wo minimum, gene a ing a wa e shed line a he end
o he p ocess.
Le us in oduce a ew concep s and no a ions abou opog aphy in o de o con inue wi h
he wa e shed ans o m. A g eyscale image may be conside ed as a g aph G= (V,A)wi h
a ini e se o V e exes (pixels) and a se o a cs A⊆V×Vde ining he connec i i y. Two
pixels uand a e connec ed i (u, )∈A. The pixels connec ed o u, called neighbo s, a e
deno ed by N(u).
The mos widely used connec i i y is ou , conside ing he o hogonal neighbo s, le ,
igh , up and down, known as Von Neumann connec i i y. Ano he a ia ion is he Moo e
neighbo hood, whe e he eigh neighbo s su ounding a pixel a e connec ed. Figu e 2.5(a)
shows a pixel wi h 4- and 8-connec i i y.
The slope be ween wo neighbo s is de ined by:
∀u∈V,∀ ∈N(u),slope(u, ) = h(u)−h( ),
whe e h(u)is he g ey alue (al i ude) o he pixel u. The lowe slope is de ined as he maximal
slope connec ing u o any o i s neighbo s o a lowe al i ude:
LS(u) = max(h(u)−h( ))| ∈Γ(u),
wi h Γ(u) he se o neighbo s wi h h( )<h(u). I Γ(u)has mo e han one elemen , NF(u)
ep esen s an a bi a y elemen o ha se .
(a) (b)
Figu e 2.5: (a) Pixel 4– and 8–connec i i y, (b) backwa d N+
G(p)and o wa d N−
G(p)neighbo hood o a pixel p
wi h 8–connec i i y.
2.3. Segmen a ion echniques 23
(a) (b)
(c) (d)
Figu e 2.6: Wa e shed based on Hill-Climbing algo i hm. Example o 1D image ep esen ed as a e ain by dashed
lines and as g ey alues by he squa es: (a) de ec ing and labelling all minima in he image wi h unique
labels (“A” and “B”), (b) and (c) con inues p opaga ing he labels upwa ds, climbing up he hill, (d)
esul o he segmen a ion in wo egions.
A pla eau is a connec ed subg aph P= (VP,AP)⊆G, whe e ∀u∈VP,h(u) = c, and cis
he al i ude o he pla eau. Thus, a pla eau is a egion o cons an g ey alue wi hin he image.
The se N=(u)deno es he pixels ∈N(u)wi h h(u) = h( ). A connec ed componen o a
g aph Gis a subg aph Pin which pixels a e connec ed o each o he by pa hs. A pla eau Pis
a le el componen o he image, conside ed as a alued g aph, i.e., a connec ed componen o
pixels o cons an g ey alue h[142].
Finally, he lowe bo de o a pla eau Pis de ined as:
∂−
P={u∈VP|∃ ∈N(u),h( )<h(u)}.
I ∂−
P=/0 he pla eau is called a minimum pla eau. All he pixels wi hin a minimum pla eau
a e also minimum. In con as , i ∂−
P6=/0 he pla eau is called a non-minimum pla eau.
Di e en algo i hms ha e been implemen ed o compu e he wa e shed ans o m using
sequen ial s uc u es as queues o g aphs o simula e he looding p ocess [142]. Al hough a -
ious implemen a ions can be ound in he li e a u e, in his hesis we ollow he Hill-Climbing
algo i hm based on he opog aphical dis ance by Meye [111]. This algo i hm s a s by de-
ec ing and labelling all minima in he image wi h unique labels, as illus a ed in Figu e 2.6(a).
The p ocess con inues by p opaga ing he labels upwa ds, climbing up he hill, ollowing he
pa h de ined by he lowe slope o each pixel, Figu e 2.6(b) and Figu e 2.6(c). The esul o
he segmen a ion, as shown in Figu e 2.6(d), is a se o egions, each one ep esen ed by a
ca chmen basin, wi h hei own label. A he end all he pixels belong o a egion and he
wa e shed lines a e he limi s be ween hese egions.
24 Chap e 2. Fundamen als
P oblems a ise o digi al images wi h pla eaus, as i is no possible o know a p io i
whe he a pla eau is minimum o non-minimum, so an addi ional p ocessing is equi ed.
The mos common solu ion is o p ep ocess he image by calcula ing i s lowe comple e im-
age [111], whe e each pixel has a leas one neighbo wi h a lowe alue, excep hose pixels
which a e minima. Ano he al e na i e is o calcula e he dis ances o an inne pixel o he
lowe bo de o he pla eau du ing he wa e shed p ocessing, which is he s a egy selec ed in
his wo k. The pseudocode o he wa e shed ans o m based on he Hill-Climbing algo i hm
is gi en in Sec ion 3.2.2 whe e i s implemen a ion based on cellula au oma a is explained in
de ail.
2.4 Cellula au oma a
Cellula Au oma a (CA) cons i u e a compu ing model ha has been ex ensi ely used o
a i icial li e [51], pa e n ecogni ion [37] o image p ocessing [143]. The popula i y o
CA is mainly due o he simplici y o modelling complex p oblems wi h he help o local
in o ma ion only. CA a e composed o a se o cells a anged in o a egula g id o one,
wo o h ee dimensions o iginally p oposed by John Von Neumann [116] as o mal models
o sel - ep oducing o ganisms. In he case o wo dimensions, each cell is connec ed o i s
ou o eigh adjacen neighbo s, depending on he connec i i y, as shown in Fig. 2.7. The
mos widely used connec i i y is he Von Neumann neighbo hood, conside ing he o hogonal
neighbo s, le , igh , up and down. The Moo e neighbo hood, whe e he eigh neighbo s
su ounding a cell a e connec ed is a a ia ion also used o connec ing cells o he au oma on.
Figu e 2.7: Cells a anged in a egula g id o wo dimensions. Cells a e connec ed o ou (le ) and eigh ( igh )
adjacen neighbo s.
2.4. Cellula au oma a 25
Figu e 2.8: Synch onous upda ing p ocess in a cellula au oma on. The upda es o he cells a e pe o med
synch onously and in disc e e ime s eps. G ey squa es ep esen cells whose s a e has changed.
Cells in a cellula au oma on can be in one o a ini e numbe o possible s a es. Each cell
changes i s s a e depending on he cu en s a e and he s a e o i s neighbo s. This equi es
a s ic o de o upda ing he au oma on, whe e a cell canno be upda ed un il all o he cells
ha e also been upda ed. The upda es o he cells a e usually pe o med synch onously and in
disc e e ime s eps. Figu e 2.8 shows an example o a 6×6 au oma on, using 8-connec i i y,
which is upda ed synch onously. As illus a ed in he igu e, he upda ing p ocess akes places
in disc e e ime s eps. The cells ha a e upda ed in his example a e shaded in g ey.
I he upda es o he cells a e no equi ed o ake place synch onously, bu each one can
be upda ed o i s nex s a e an unbounded numbe o imes wi hou synch oniza ion, hen we
ha e an asynch onous au oma on [115]. In his case, he g id can be pa i ioned in o di e en
egions which can be upda ed independen ly. I is possible o igno e he synch oniza ion
poin s associa ed o he e olu ion o he au oma on, esul ing in a so-called asynch onous
au oma on. In his case, howe e , he co ec ness and con e gence o he algo i hm could be
se e ely a ec ed [4]. In o de o e icien ly de elop asynch onous compu ing schemes, i is
impo an o in es iga e he non-de e minis ic and p obabilis ic beha io associa ed o such
schemes [2].
Two dimensional CA can be di ec ly mapped in o 2D images whe e each cell in he au-
oma on co esponds o a pixel in he image. The connec i i y used in he au oma on is de-
no ed in he image by N(u). The same can be applied o 3D cellula au oma a and 3D
images by modi ying he connec i i y o ake in o accoun he hi d dimension.
26 Chap e 2. Fundamen als
(a) (b) (c)
Figu e 2.9: (a) O iginal image, (b) e osion (sh inks b igh e objec s), and (c) dila ion (expands b igh e objec s).
The SE was a squa e o 5×5 pixels.
2.5 Ma hema ical mo phology
In his sec ion we p esen an o e iew o Ma hema ical Mo phology (MM) ope a o s. In
pa icula , we desc ibe mo phological ope a o s based on he geodesic econs uc ion, which
a e ools de ined in he MM amewo k [152].
The Ma hema ical Mo phology (MM) is a heo y o analyzing and p ocessing spa ial
s uc u es om images [149]. The echniques a e based on wo basic ope a o s, e osion (ε)
and dila ion (δ), om which a se o ad anced analysis ools is cons uc ed.
E osion and dila ion ans o m an image Iusing a s uc u ing elemen (SE), gi ing as
ou pu o each pixel p he in imum (V)o sup emum (W), espec i ely, o he in ensi y
alues o he se o pixels included by he SE when i is cen e ed on p. Gene ally speaking,
he e osion ope a o sh inks objec s ha a e b igh e han hei su oundings, whe eas he
dila ion ope a o expands hem. Figu e 2.9 shows he e osion and dila ion o he image o
Lena using a squa e SE o 5×5 pixels.
2.5.1 Opening and closing by econs uc ion
The dila ion o an e oded image is known as opening, γ(I). Con e sely, he e osion o a
dila ed image is known as closing, φ(I). The opening ope a o la ens b igh objec s o
an image i he SE i s wi hin he objec s, and he closing ope a o has he opposi e e ec .
The e o e, opening and closing a e used o ex ac in o ma ion ela ed o he shape and size
o he objec s. Howe e , opening and closing a e no connec ed il e s; i.e., hese ope a o s
2.5. Ma hema ical mo phology 27
(a) (b) (c)
Figu e 2.10: A subse o 256×256 pixels o he image o Lena. (a) e osion by a SE o 5×5 pixels, (b) opening,
and (c) opening by econs uc ion.
do no p ese e edges be ween objec s as hey wo k on pixels a he han image s uc u es.
Fo ins ance, adjacen egions can be me ged in o one, and hus his biases he analysis o he
spa ial dis ibu ion.
I is possible o cons uc opening and closing ope a o s based on he geodesic econs uc-
ion o comple ely p ese e o emo e he spa ial s uc u es o an image i he SE i s (o no )
wi hin he objec s [149]. The geodesic dila ion o an image I( he mask) om J( he ma ke )
is de ined as:
δ(1)
I(J) = δ(1)(J)∧I,(2.11)
whe e δ(1)deno es he elemen a y dila ion and ∧ he poin -wise minimum.
The opening by econs uc ion γ(n)
(I)o an image Iis de ined as he econs uc ion by
dila ion o I om he e osion wi h a SE o size no I. Fi s , he image is ans o med by an
e osion εn(I)c ea ing a ma ke image J. Then, econs uc ion by dila ion Rδ
Iis an i e a i e
p ocess ha applies geodesic dila ion on he ma ke image un il s abili y (δ(n)
I=δ(n+1)
I):
Rδ
I(J) = δ(n)
I(J) = δ(1)
Ihδ(n−1)
I(J)i.(2.12)
The econs uc ion pe mi s he ull e ie al o all hose s uc u es ha we e no comple ely e-
mo ed by he e osion. Thus, he mo phological econs uc ion needs se e al i e a ions be o e
s abili y is a ained. Figu e 2.10 shows he esul o opening and opening by econs uc ion
o e a subse o 256×256 pixels o he image o Lena. I can be obse ed in Figu e 2.10(b)
ha he edges in he hai o in he ea he s o he ha a e no p ese ed in he opening. How-
28 Chap e 2. Fundamen als
e e , in Figu e 2.10(c) he s uc u es o he hai and ea he s ha we e no comple ely emo ed
by he e osion a e success ully econs uc ed by opening by econs uc ion.
By duali y, he closing by econs uc ion φ(n)
(I)o an image Iis de ined as he econ-
s uc ion by e osion o I om he dila ion wi h a SE o size no I.
2.5.2 A ibu e il e ing
O en, a classic image analysis p ep ocessing p oblem consis s o il e ing ou small ligh
(o da k) pa icles om g eyscale images wi hou damaging he emaining s uc u es [170].
Opening and closing by econs uc ion a e good ope a o s o his ask. Howe e , hese ope -
a o s only ex ac in o ma ion ela ed o he size o he objec s. The e o e, i he s uc u es o
be p ese ed a e elonga ed objec s, hey can be comple ely emo ed.
Mo phological a ibu e il e s a e connec ed ope a o s ha p ocess an image acco ding
o a c i e ion [25], such as he a ea o he s anda d de ia ion o he pixel in ensi y, emo ing
pla eaus (connec ed componen s) ha do no sa is y a gi en c i e ion. Mo phological a ibu e
il e s a e connec ed il e s. The ollowing de ini ions a e o bina y images, al hough gene -
aliza ion o g ey-scale images can be achie ed h ough h eshold decomposi ion [76].
The connec ed opening Γxo a se Xa a poin xis de ined as:
Γx(X) =
Xi x∈X,
/0 o he wise.
(2.13)
Figu e 2.11 shows an example o a connec ed opening on a bina y image wi h a se Xconsis -
ing o h ee connec ed componen s, named C1
1,C2
1, and C3
1. The i- h componen is indica ed
by he supe sc ip , and he backg ound (0) o o eg ound (1) is indica ed by he subsc ip .
The opening Γxp ese es only ha connec ed componen in Xwhich con ains he pixel x, as
illus a ed in Figu e 2.11(b).
A i ial opening ΓTuses an inc easing c i e ion T o il e connec ed componen s and i
is de ined as ollows [150]:
ΓT(C) =
Ci Csa is ies c i e ion T,
/0 o he wise.
(2.14)
The i ial opening p ese es he connec ed componen s o which he inc easing c i e ion T
holds. Fo example, he ollowing is an inc easing c i e ion: mus ha e an a ea o λpixels o
mo e [25].
2.5. Ma hema ical mo phology 29
(a) (b)
Figu e 2.11: Example o a connec ed opening. (a) Bina y image wi h h ee connec ed componen s named C1
1,C2
1,
and C3
1, and (b) he connec ed opening Γxindica ed by he in e sec ion o he do lines.
The a ibu e opening ΓTo a se Xcombines he connec ed opening (2.13) and he i ial
opening (2.14) and is de ined as ollows:
ΓT(X) = [
x∈X
ΓT(Γx(X)).(2.15)
The a ibu e opening is he union o all connec ed componen s o Xwhich mee he c i e ion
T. The a ibu e opening can be explained by using a ee ep esen a ion o he image, as
illus a ed in Figu e 2.12(b). The oo o he ee ep esen s he backg ound o he image, and
he lea es co esponds o he connec ed componen s in he o eg ound. The a ibu e il e ing,
(a) (b) (c) (d)
Figu e 2.12: Example o a a ibu e opening. (a) Bina y image wi h h ee connec ed componen s named C1
1,C2
1, and
C3
1, (b) ee ep esen a ion o he image, (c) a ibu e il e ing emo ing a node o he ee, and (d) he
inal esul .
36 Chap e 2. Fundamen als
The classi ica ion phase is pe o med by compu ing he sign o he ollowing decision
unc ion:
D(x) = ∑
i∈S
αiyi(xi·x)+b,(2.24)
whe e αia e he nonze o Lag ange mul iplie s, Sis he subse o aining samples xi, and xis
he unknown sample. The pa ame e s (αi,S,b)a e ound du ing he aining phase. Fo each
x, he co esponding class is +1 i D(x)>0 and −1 o he wise.
Al hough he solu ion may be de e mined op imally by he SVM when he aining sam-
ples a e no linea ly sepa able, he SVM app oach uses ke nel icks o map he non-linea ly
sepa able da a in o a highe dimensional space, in o de o enhance linea sepa abili y be ween
he wo classes. Se e al ypes o ke nels, such as linea , polynomial, splines o Radial Basis
Func ion (RBF) ke nels can be used in SVM classi ie s. We e e he eade o [1, 72, 27] o
u he de ails on SVM and ke nel icks.
Fo hype spec al image classi ica ion, he Gaussian RBF has been widely used. The
disc iminan unc ion (2.24) can be exp essed using he RBF ke nel as:
D(x) = ∑
i∈S
αiyiexp−γ||xi−x||2+b,(2.25)
whe e exp(−γ||xi−x||2)is he RBF ke nel and γis a posi i e pa ame e con olling he wid h
o he ke nel.
2.7.1 5- old c oss alida ion
The SVM is mainly a nonpa ame ic me hod, al hough some pa ame e s need o be uned
be o e he op imiza ion. In he RBF ke nel case, he e a e wo pa ame e s: C, which con ols
he penal y e m, and γ, which is he wid h o he ke nel. The bes pa ame e s a e usually ound
by k– old c oss- alida ion, whe e se e al pa ame e s a e es ed, o example by a sea ch in a
ange o alues (g id sea ch).
Gi en a se o aining samples, he k- old c oss alida ion di ides he o al numbe o
samples in o kpa i ions. One pa i ion is used o alida e he accu acy o he classi ica ion,
and he emaining k−1 pa i ions a e used as aining da a. This alida ion is epea ed k
imes, using each pa i ion once as a es . The inal classi ica ion accu acy is de e mined by
he a e age wi h he kclassi ica ion esul s. In his wo k we ha e used 5– old c oss alida ion
o uning he SVM pa ame e s.
2.7. Pixel-wise classi ica ion by SVM 37
2.7.2 Mul i-class SVM classi ica ion
The s anda d SVM classi ie is designed o wo-class p oblems. When he da a ha e K>2
classes a me hod o sol ing he mul iclass p oblem mus be de ined. These me hods may
be o he ype one-agains -all (OAA), one-agains -one (OAO) and all-a -once, whe e a se o
bina y classi ie s is combined. In he OAA app oach, he Kclass p oblem is con e ed in o K
bina y classi ie s whe e he i h classi ie sepa a es he class i om he emaining classes. The
OAO mul iclass app oach c ea es T=K(K−1)/2 bina y classi ie s on each pai o classes,
whe e Kis he numbe o classes. The inal classi ica ion o each poin is gi en by he
highes numbe o o es ob ained o a class in he Tclassi ie s. Hsu and Lin [80] ound ha
he OAO app oach is mo e sui able o p ac ical use han he o he me hods, mainly because
he aining ime is sho e . This is he app oach used in all he SVM classi ica ions ca ied
ou in his wo k.
2.7.3 LIBSVM: he ac o lib a y o SVM
In his sec ion we p esen he ac o lib a y o SVM (LIBSVM) and he p incipal in e aces
and ex ensions ha a e based on his lib a y. LIBSVM [35] is a lib a y o Suppo Vec o
Machine (SVM) w i en in C, widely used in machine lea ning. The lib a y implemen s he
One-Agains -One app oach o mul iclass classi ica ion. I is cu en ly one o he mos widely
used SVM so wa e and i has been ex ended o hi d-pa y so wa e such as Weka3, R4,
Oc a e and Ma lab5.
Owing o i s popula i y, i has been also implemen ed in o he languages such as Ja a5,
Py hon5and C#6, as well as in o he a chi ec u es, such as Cell p ocesso s and GPUs.
While e icien algo i hms o aining SVM a e a ailable, dealing wi h la ge da ase s
makes aining and classi ica ion a compu a ionally challenging p oblem. In [109] he aining
phase implemen ed in he LIBSVM is speeded up by pa allel compu a ion in Cell p ocesso
a chi ec u es. LIBSVM has also been accele a ed wi h GPUs using CUDA [8]. This GPU-
accele a ed LIBSVM implemen a ion is a modi ica ion o he o iginal LIBSVM ha exploi s
CUDA wi h he same unc ionali y and in e ace o LIBSVM. A comp ehensi e lis o o he
SVM implemen a ions and w appe s can be ound in [60]. In his hesis we ha e implemen ed
3h ps://weka.wikispaces.com/LibSVM/
4h p://c an. -p ojec .o g/web/packages/e1071/
5Ma lab, Oc a e, Ja a and Py hon implemen a ions a e included in he LIBSVM package.
6h ps://gi hub.com/cce han/LibSVMsha p/
38 Chap e 2. Fundamen als
a new GPU p oposal (GPUSVM) o he classi ica ion s age, and he LIBSVM [35] has been
used as a basis o e alua ing he p oposed schemes in CPU.
2.8 Pa allel p og amming models
This sec ion desc ibes he OpenMP and CUDA p og amming models. Fi s , we will desc ibe
OpenMP, an API o w i ing CPU mul i- h eaded applica ions on sha ed memo y a chi ec-
u es. Then, we in oduce he Compu e Uni ied De ice A chi ec u e (CUDA) de eloped by
NVIDIA, a pa allel compu ing pla o m and a p og amming model ha le e ages he high
compu a ional h oughpu o NVIDIA GPUs. We will highligh he majo di e ences ound
in he di e en GPU a chi ec u es used in his wo k.
2.8.1 OpenMP
OpenMP is he s anda d Applica ion P og am In e ace (API) o mul i- h eaded pa allel p o-
g amming on sha ed memo y a chi ec u es [120]. Communica ion and coo dina ion be ween
h eads is exp essed h ough ead/w i e ins uc ions o sha ed a iables and o he synch oniza-
ion mechanisms. I comp ises compile di ec i es, lib a y ou ines and en i onmen a iables
and is based on a o k-join model, as illus a ed in Figu e 2.18 whe e a mas e h ead c ea es a
eam o h eads ha wo k oge he in a Single P og am Mul iple Da a (SPMD) way (di e en
co es execu e di e en h eads ope a ing on di e en da a).
In sha ed memo y a chi ec u es, OpenMP h eads access he same global memo y whe e
da a can be sha ed among hem o can be p i a e o each one. F om a p og amming pe -
spec i e, da a ans e o each h ead is anspa en and synch oniza ion is mos ly implici
(see Figu e 2.18). When a h ead en e s a pa allel egion, i becomes he mas e , c ea es a
h ead eam and o ks he execu ion o he code among he h eads and i sel . A he end
o he pa allel egion, he h eads join oge he and he mas e esumes he execu ion o he
sequen ial code.
Di e en ypes o wo ksha ing cons uc s can be used o sha e he wo k o a pa allel egion
among he h eads [33]. The loop cons uc dis ibu es he i e a ions o one o mo e nes ed
loops in o chunks, among he h eads in he eam. By de aul , he e is an implici ba ie a
he end o a loop cons uc . The way he i e a ions a e spli depends on he schedule used in
he loop cons uc [33]. On he o he hand, he single cons uc assigns he wo k on only one
o he h eads in he eam. The emaining h eads wai un il he end o he single cons uc
2.8. Pa allel p og amming models 39
Figu e 2.18: OpenMP o k-join pa allel model. A mas e h ead c ea es a eam o h eads ( o k) o wo k in pa allel.
When all he h eads end hei ask, hey a e joined oge he .
owing o an implici ba ie . This ype o cons uc is also known as non-i e a i e wo ksha ing
cons uc . O he ypes o wo ksha ing cons uc s a e a ailable.
Al hough he e a e implici communica ions be ween h eads h ough access o sha ed
a iables o he implici synch oniza ion a he end o pa allel egions and wo ksha ing con-
s uc s, explici synch oniza ion mechanisms o mu ual exclusion a e also a ailable in OpenMP.
These a e c i ical o a omic di ec i es, lock ou ines, and e en synch oniza ion di ec i es.
OpenMP is no esponsible o he managemen o he memo y hie a chy bu ce ain issues
ega ding cache memo y managemen should be bo ne in mind. The e a e wo ac o s ha
de e mine whe he a loop schedule is e icien : da a locali y and wo kload balancing among
i e a ions. The bes schedule ha we can choose when he e a e da a locali y and a good
wo kload balance is s a ic wi h a chunk size o q=n/p, whe e nis he numbe o i e a ions
and p he numbe o h eads. In o he cases, dynamic o guided schedules may be adequa e.
When a cache line, sha ed among di e en p ocesso s, is in alida ed as a consequence
o di e en p ocesso s w i ing in di e en loca ions o he line, alse sha ing occu s. False
sha ing mus be a oided as i dec eases pe o mance due o cache ashing. One way o a oid
his is o di ide he da a o be accessed by di e en p ocesso s in o pieces whose size is
mul iple o he cache line size. A good p ac ice o imp o ing cache pe o mance is o choose
a schedule wi h a chunk size ha minimizes he eques s o new chunks and ha is a mul iple
o a cache line size.
40 Chap e 2. Fundamen als
2.8.2 CUDA
The NVIDIA Compu e Uni ied De ice A chi ec u e (CUDA) is a pa allel compu ing pla o m
and a p og amming model. The GPU p o ides massi ely pa allel p ocessing capabili ies wi h
a high compu a ional h oughpu due o hei la ge numbe o co es. In pa icula , CUDA is
o ganized in o a se o S eaming Mul ip ocesso s (SMs), each one con aining many Scala
P ocesso (SP) wi h many co es inside. The NVIDIA’s G80 se ies, in oduced in No em-
be 2006, had a o al o 128 co es in 16 SMs, each one wi h 8 SPs, as summa ized in Figu e
2.19(a). This a chi ec u e uses a Single Ins uc ion, Mul iple Th ead (SIMT) pa allel p og am-
ming model. SIMT is he e minology used by NVIDIA o de ine a hyb id model be ween
ec o p ocessing (SIMD) and ha dwa e h eading [40]. This app oach makes i possible o
w i e single ins uc ions which will be simul aneously execu ed om mul iple h eads. The
gene al speci ica ion, as well as he numbe o esou ces a ailable on he GPU depends on
i s compu e capabili y (CC), which is ep esen ed by a e sion numbe , 1.x, 2.x, 3.x and
5.x [119]. The i s CUDA capable ha dwa e, codenamed esla, has a CC o 1.x and de ines
he main ea u es o he a chi ec u e, such as he o ganiza ion in o a se o SMs, SPs and he
di e en ypes o de ice memo y. A ull lis o he di e ences among each compu e capabili y
can be ound in [119, 40].
The basic compu e uni in CUDA is he SM which has ixed and limi ed esou ces, such
as a se o egis e s and on-chip memo y ha a e sha ed among he co es wi hin he same SM.
The GPU can manage and schedule housands o h eads in ha dwa e simul aneously, a oiding
high h ead managemen o e heads. A la ge numbe o h eads a e equi ed o make ull use
o he GPU compu ing capabili ies. The h eads execu e he same ins uc ion on di e en da a
by g ouping 32 h eads as he minimum size o collabo a i e uni , called a wa p. The wa p
size is implemen a ion de ined and i is ela ed o sha ed memo y o ganiza ion, da a access
pa e ns and da a low con ol [90].
The h eads a e a anged in a 1D, 2D o 3D g id o blocks which a e scheduled o any o
he a ailable SMs. Figu e 2.19(a) shows a 2D g id o 8 blocks each one wi h 4×4 h eads.
Each h ead has a unique ID ha iden i ies which block he h ead belongs o, and he h ead’s
posi ion wi hin he block. The g id o blocks is usually designed o ma ch a h ead wi h a alue
among he di e en da a ha will be p ocessed on he GPU.
One o he mos impo an aspec s o he a chi ec u e is he memo y hie a chy as i plays
a key ole in pe o mance. As shown in Figu e 2.19(a), he G80 a chi ec u e (CC 1.0) has
a global memo y, a ex u e memo y and a cons an memo y which a e a ailable o all he
2.8. Pa allel p og amming models 41
(a) (b)
Figu e 2.19: CUDA. (a) O e iew o G80 a chi ec u e, (b) g id o blocks and block o h eads scheduled o any o
he a ailable SMs.
h eads a any S eaming Mul ip ocesso . The e was no a L1 / L2 cache hie a chy o caching
global memo y da a on he ea ly GPU a chi ec u es. The e o e, he de ice memo y was de-
signed o speci ic pu poses.
The global memo y is he main de ice memo y on he GPU, and has he slowes access
ime. Howe e , he numbe o memo y accesses o global memo y can be educed o ce ain
memo y access pa e ns by a echnique known as coalescing. I h eads wi hin he wa p7
eques consecu i e and aligned alues in memo y, he de ice coalesces he global memo y
ansac ions (load/s o e) in o as ew ansac ions as possible (one in he bes case) [119].
Da a alloca ed in he ex u e memo y space will be au oma ically cached. The e a e only
8 KB o cache pe SM and i is op imized o 2D spa ial locali y. This can imp o e pe o -
mance when h eads access alues in some egula spa ial neighbo hood. Tex u e memo y is
gene ally used o isualiza ion o as inpu bu e s owing o da a caching.
The cons an memo y is ano he possibili y o caching accesses (64 KB in o al) o global
memo y. A single ead om cons an memo y can be b oadcas o a wa p, i he same alue is
accessed by all he h eads wi hin he wa p. As a esul , eading om his memo y cos s one
memo y ansac ion om global memo y he i s ime da a a e accessed, and one ead om
he cons an cache o he wise.
The on-chip memo y, known as sha ed memo y, enables ex emely apid load/s o e ac-
cesses o he da a bu wi hin he li e ime o he block. The e a e 16 KB o sha ed memo y
7On ha dwa e o compu e capabili y 1.x, memo y ansac ions a e coalesced wi hin hal wa p.
42 Chap e 2. Fundamen als
wi hin each SM bu i is only “sha ed” o he h eads o he same block. The e o e, sha -
ing da a among di e en blocks is no possible h ough his memo y and becomes a challenge
when p og amming o he GPU. I is up o he p og amme loading da a om global ( ex u e)
memo y o sha ed memo y. The main ea u e o he sha ed memo y is eusing da a wi hin a
block, sha ing da a among he h eads o he same block. This way, he sha ed memo y can
be managed as an explici cache de ined by he p og amme . Al hough he amoun o sha ed
memo y pe SM is only 16 KB, he e ec i e use o his memo y can lead o speedups o 7×
compa ed o a nai e implemen a ion in global memo y [40].
Each h ead on he GPU has i s own local memo y and a se o egis e s whe e he compu-
a ion akes place. The maximum numbe o egis e s ha can be used by a h ead is limi ed
by he CC o he GPU, as well as he numbe o h eads con igu ed pe block [119].
Di e en aspec s mus be aken in o conside a ion o e icien ly exploi all he memo y on
he GPU [90]. Fo example: (1) da a ans e be ween he CPU and he GPU should be min-
imized; (2) he memo y access pa e n mus be coalesced o consecu i e memo y loca ions;
(3) da a loaded in sha ed memo y should be eused o educe load/s o e accesses o he global
memo y; (4) he numbe o h eads pe block mus be op imized o un he maximum con-
cu en h eads allowed in each SM; and (5) minimizing he global synch oniza ion among
blocks leads o a educ ion in he execu ion ime o he p og am. Paying a en ion o hese
aspec s is i al o GPU p og amming.
In Fe mi (CC 2.x), Keple (CC 3.x) and Maxwell (CC 5.x) a chi ec u es, he e is also an L1
and L2 cache hie a chy, as shown in Figu e 2.20 o Keple . The accesses o global memo y
a e cached in his memo y hie a chy. The L2 cache is ully a ailable o all he h eads and he
L1 cache only o he h eads unning in he same S eaming Mul ip ocesso (in Keple , he
SMs a e called SMXs). No e ha he L1 and L2 caches a e managed by he GPU, unlike he
sha ed memo y, bu he p og amme can ake ad an age o his cache hie a chy by exploi ing
he memo y access pa e n when eading da a om he global memo y ( he same when w i ing
da a o he global memo y). The L1 cache is placed in he same chip as he sha ed memo y,
so he size o he on-chip memo y pe SMX (see Figu e 2.20) is spli be ween hese wo kind
o memo ies.
In he ollowing, we will co e he majo cha ac e is ics ound in he CC 2.x and 3.x co -
esponding o he GPUs used in his wo k. The main di e ences a e summa ized in Table 2.1.
The main changes in oduced in CC 2.x a e: (i) ex ension in size o he sha ed memo y om
16 KB up o 48 KB pe SM, (ii) con igu able 16 KB o 48 KB o L1 cache on each SM,
2.8. Pa allel p og amming models 43
Figu e 2.20: O e iew o he Keple a chi ec u e inco po a ing a L1 and L2 cache hie a chy.
and (iii) sha ed L2 cache o all SMs. The CC 3.x mainly inc eases he numbe o esou ces
a ailable pe h ead, SP and SMX compa ed o CC 2.x. The CC 3.5 has a ead-only cache o
48 KB sha ed by e e y h ee SMXs.
In all he a chi ec u es, h eads wi hin he same block can be synch onized, o example
o communica e in e media e esul s in he sha ed memo y as pa o a pa allel compu a ion.
Howe e , i is no possible o synch onize h eads among di e en blocks. Owing o his
es ic ion, he communica ion among all he h eads mus be h ough he global memo y and
his becomes ano he challenge when a h ead needs da a which ha e been gene a ed ou side
i s block.
44 Chap e 2. Fundamen als
G80 Fe mi GF110 Keple GK104 Keple GK110
Compu e capabili y 1.0 2.0 3.0 3.5
Max SMs 8 16 8 15
CUDA co es pe SM 8 32 192 192*
Max h eads pe block 512 1024 1024 1024
Max o al h eads pe SM 768 1536 2048 2048
Max numbe o blocks pe SM 8 8 16 16
Max Sha ed Mem 16 kB 48 kB 48 KB 48 KB
Max L1 cache N/A 48 kB 48 KB 48 KB
Max L2 cache N/A 768 KB 512 KB 1536 KB
Max Memo y 1536 MB 1536 MB 2048 MB 6144 MB
*Plus an addi ional 64 dual-p ecision uni s pe SM.
Table 2.1: Max GPU esou ces de ined by he compu e capabili y.
A CUDA p og am is called a ke nel and i is execu ed on he GPU by housands o h eads
in pa allel. A ke nel is con igu ed by speci ying he g id size, he h eads wi hin he block,
and he amoun o sha ed memo y used by a block. When a ke nel is called, he compu a ion
on he GPU akes place. The blocks, which a e a anged in o a g id, a e scheduled o any o
he a ailable co es enabling au oma ic scalabili y o u u e a chi ec u es.
2.9 Expe imen al se up
In his hesis we ha e aken in o accoun he e icien compu a ion on GPU o he echniques
unde s udy. In ecen yea s, GPUs (and he CUDA API) ha e e ol ed so apidly ha we ha e
e alua ed ou wo k on di e en a chi ec u es (and CUDA e sions). In his sec ion we p esen
he main speci ica ions o he CPU and GPUs used in ou expe imen s. The expe imen s a e
execu ed unde Linux using he gcc compile e sion 4.6.3 o he OpenMP implemen a ions,
and he n cc compile o he case o he CUDA implemen a ions, espec i ely, wi h ull op-
imiza ion lags (-O3) in bo h cases. We desc ibe he pe o mance measu es o e alua e he
classi ica ion esul s in e ms o accu acy, as well as in e ms o execu ion ime and speedup.
Di e en da ase s ha e been used in his wo k and will be also de ailed in his sec ion. The
names and numbe o known samples ( e e ence map) o he hype spec al images a e sum-
ma ized a he end o his sec ion.
2.9. Expe imen al se up 45
2.9.1 Ha dwa e used in he expe imen s
In his wo k we ha e used an In el quad-co e i7-860 mic op ocesso (8MB Cache, 2.80 GHz)
and 8 GB o RAM as he base a chi ec u e o compa ison. Each co e has a sepa a ed L1
cache o ins uc ions and da a, and a uni ied L2 cache. The uni ied L3 cache is common o
all he co es. The main cha ac e is ics o he memo y hie a chy a e desc ibed in de ail in [82].
Table 2.2 summa izes he main speci ica ions o his CPU.
We ha e used he NVIDIA GTX 580, GTX 680 and GTX TITAN de ices. Table 2.3
shows he GPU model, he compu e capabili y o he g aphic ca ds, a ailable esou ces, and
CUDA e sions used in his hesis.
# co es Co e clock RAM L1 L2 L3
(GHz) (GB) (KB) (KB) (KB)
In el co e i7-860 4 2.80 8 64/64 256 8192
Table 2.2: Main cha ac e is ics o he CPU used in his hesis.
GTX 580 GTX 680 GTX TITAN
Compu e capabili y 2.0 3.0 3.5
S eaming Mul ip ocesso s 16 8 15
CUDA co es pe SM 32 192 192*
Th eads pe block 1024 1024 1024
To al h eads pe SM 1536 2048 2048
Numbe o blocks pe SM 8 16 16
Ac i e wa ps pe SM 48 64 64
Regis e s pe SM 32768 65536 65536
Regis e s pe h ead* 63 63 63
De ice Memo y 1536 MB 2048 MB 6144 MB
Sha ed Memo y 48 KB 48 KB 48 KB
L1 cache 48 KB 48 KB 48 KB
L2 cache 768 KB 512 KB 1536 KB
CUDA e sion 4.0 5.0 5.5
*Plus an addi ional dedica ed ze o egis e .
Table 2.3: GPU model, compu e capabili y, esou ces and CUDA e sion o he g aphic ca ds used in his hesis.
52 Chap e 2. Fundamen als
Indian Pines Salinas Valley
Classes Numbe Classes Numbe
o samples o samples
1-Al al a 54 1-B ocoli_g een_weeds_1 2009
2-Co n-no ill 1434 2-B ocoli_g een_weeds_2 3726
3-Co n-min ill 834 3-Fallow 1976
4-Co n 234 4-Fallow_ ough_plow 1394
5-G ass/pas u e 497 5-Fallow_smoo h 2678
6-G ass- ees 747 6-S ubble 3959
7-G ass/mowed 26 7-Cele y 3579
8-Hay-wind owed 489 8-G apes_un ained 11271
9-Oa s 20 9-Soil_ inya d_de elop 6203
10-Soybean-no ill 968 10-Co n_senesced_g een_weeds 3278
11-Soybean-min ill 2468 11-Le uce_ omaine_4wk 1068
12-Soybean-clean 614 12-Le uce_ omaine_5wk 1927
13-Whea 212 13-Le uce_ omaine_6wk 916
14-Woods 1294 14-Le uce_ omaine_7wk 1070
15-Bld-G s-T s-D s 380 15-Vinya d_un ained 7268
16-S one-S eel 95 16-Vinya d_ e ical_ ellis 1807
To al 10366 To al 54129
Table 2.7: To al numbe o samples o AVIRIS da ase s: Indian Pines and Salinas Valley.
Hekla Volcano
Classes Numbe Classes Numbe
o samples o samples
1-Andesi e la a 1970 342 7-Hyaloclas i e o ma ion 684
2-Andesi e la a 1980 I 708 8-La a co e ed 700
3-Andesi e la a 1980 II 1496 9-Rhyoli e 404
4-Andesi e la a 1991 I 2739 10-Sco ia 550
5-Andesi e la a 1991 II 410 11-Fi n and glacie ice 458
6-Andesi e la a wi h moss 1023 12-Snow 713
To al =10227
Table 2.8: To al numbe o samples o AVIRIS da ase : Hekla Volcano.
The Indian Pines scene was acqui ed o e a mixed ag icul u al/ o es ed egion in no h-
wes e n Indiana wi h a mode a e spa ial esolu ion o 20 m. This image ep esen s a e y
challenging land-co e classi ica ion scena io. I consis s o 145×145 pixels and 220 spec al
2.9. Expe imen al se up 53
bands. The ou bands co e ing he egion o wa e abso p ion we e emo ed. This da ase
is a ailable h ough Pu due’s Uni e si y Mul iSpec si e. Figu e 2.25(a) shows he ue colo
ep esen a ion o he scene. The six een classes o in e es a ailable in he e e ence map a e
shown in Figu e 2.25(b). The o al numbe o samples a e p esen ed in Table 2.7. The numbe
o aining samples o his scene is usually andomly aken om he e e ence map as 5% o
10% o he a ailable da a.
The Salinas da ase has 512×217 pixels and i was cap u ed o e he Salinas Valley in
Cali o nia. I is cha ac e ized by a high spa ial esolu ion (3.7 m) owing o a low-al i ude ligh
du ing he acquisi ion [72]. None o he hype spec al bands was emo ed in his da ase . The
o al numbe o samples a e p esen ed in Table 2.7, and like he Indian Pines, he aining
samples a e andomly aken om he e e ence map as 5% o 10% o he a ailable da a.
Figu e 2.26(a) shows he ue colo ep esen a ion o he scene, and Figu e 2.26(b) shows he
e e ence map.
The Hekla olcano scene has spa ial dimensions o 560×600 pixels wi h a spa ial es-
olu ion o 20 m. Du ing da a collec ion o his da ase , spec ome e ou was no p ope ly
wo king. This pa icula spec ome e ope a es in he nea -in a ed wa eleng h ange, om
1.84 µm o 2.4µm (64 da a channels). These 64 da a channels we e dele ed om he da a se
along wi h he i s channels o all he o he spec ome e s, bu hose channels we e blank.
Once he noisy and blank da a channels had been emo ed, 157 da a channels we e le [16].
Figu e 2.27(a) shows a alse colo ep esen a ion o he scene. The wel e classes o in e es
a ailable in he e e ence map a e shown in Figu e 2.27(b). The names and he numbe o
samples pe class a e a ailable in Table 2.7. Fo his da ase , a ixed numbe o i y samples
pe class is used o aining, and he es o he samples a e used o es ing.
Table 2.9 summa izes he dimensions and he size in MB o he i e hype spec al im-
ages used in he expe imen s ca ied ou in his hesis. We ha e conside ed di e en spa ial
esolu ions (1.3µm, 3.7µm and 20 µm), di e en dimensions in he spa ial domain ( om
145×145 o 1096×715 pixels), and di e en numbe s o spec al bands ( om 102 o 224
bands). The Pa ia Ci y scene is he la ges in he spa ial domain wi h 1096×715 pixels, while
he scenes o Indian Pines and Salinas Valley a e he scenes wi h mo e spec al bands, 220
and 224, espec i ely.
The Pa ia Uni e si y, Pa ia Ci y, Indian Pines and Salinas Valley da ase s (hype spec-
al image and e e ence map) a e publicly a ailable online9a he esea ch webpage o he
9h p://www.ehu.eus/ccwin co/index.php? i le=Hype spec al_Remo e_Sensing_Scenes
54 Chap e 2. Fundamen als
Da ase name Dimensions Size (MB) Senso
Pa ia Uni e si y 610×340×103 162.9 ROSIS-03
Pa ia Ci y 1096×715×102 609.8 ROSIS-03
Indian Pines 145×145×220 35.3 AVIRIS
Salinas Valley 512×217×224 189.9 AVIRIS
Hekla Volcano 560×600×157 402.5 AVIRIS
Table 2.9: Hype spec al images used in his wo k.
Compu a ional In elligence G oup om he Basque Uni e si y (UPV/EHU). The Indian Pines
scene is o iginally a ailable h ough Pu due’s Uni e si y Mul iSpec si e10.
We would like o hank p o . Benedik sson om he Uni e si y o Iceland, o p o iding
he hype spec al da ase o Hekla.
10h p://enginee ing.pu due.edu/~biehl/Mul iSpec/hype spec al.h ml
2.9. Expe imen al se up 55
(a) (b)
(c)
Figu e 2.23: Pa ia Uni e si y da ase . T ue colo ep esen a ion (a), e e ence map wi h nine classes o in e es (b),
and name o he classes (c).
56 Chap e 2. Fundamen als
(a) (b)
(c)
Figu e 2.24: Pa ia Ci y da ase . T ue colo ep esen a ion (a), e e ence map wi h nine classes o in e es (b), and
name o he classes (c).
2.9. Expe imen al se up 57
(a) (b) (c)
Figu e 2.25: Indian Pines da ase . T ue colo ep esen a ion (a), e e ence map wi h six een classes o in e es (b),
and name o he classes (c).
(a) (b) (c)
Figu e 2.26: Salinas Valley da ase . T ue colo ep esen a ion (a), e e ence map wi h six een classes o in e es (b),
and name o he classes (c).
58 Chap e 2. Fundamen als
(a) (b)
(c)
Figu e 2.27: Hekla Volcano da ase . False colo ep esen a ion (a), e e ence map wi h wel e classes o in e es
(b), and name o he classes (c).
CHAPTER 3
SPECTRAL-SPATIAL CLASSIFICATION
SCHEMES BASED ON SEGMENTATION AND
MATHEMATICAL MORPHOLOGY
3.1 In oduc ion
In his chap e we p esen he wo schemes we p oposed o e icien spec al-spa ial nD image
classi ica ion, based on segmen a ion, Ma hema ical Mo phology (MM), and SVM classi ie s,
called CA–WSHED–MV and WT–EMP.
Fi s , we desc ibe in Sec ion 3.1.1 he gene al amewo k o spec al (pixel-wise) clas-
si ica ion schemes as a basis o designing new schemes. This amewo k is a s a ing poin
o hype spec al image classi ica ion. Second, a gene al scheme o spec al-spa ial classi-
ica ion, as well as he common da a usion s a egies o joining he spec al and he spa ial
in o ma ion o such scheme a e desc ibed in his chap e in Sec ion 3.1.2. This amewo k
inco po a es spa ial in o ma ion o imp o e he esul s o he inal classi ica ion. Based on he
app oach used o ex ac ing he spa ial in o ma ion, di e en da a usion echniques can be
employed.
The spec al-spa ial CA–WSHED–MV scheme, o iginally p oposed in [155], is p esen ed
in Sec ion 3.2. In his scheme ex ac s he spa ial in o ma ion by a wa e shed ans o m based
on cellula au oma a (CA–Wa e shed), esul ing in a mo e e icien s ep o GPU p ocessing,
combining he spec al esul s o he classi ie by a Majo i y Vo e (MV).
60 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
The spec al-spa ial WT–EMP scheme is a new p oposal o land-co e classi ica ion in
emo e sensing imaging o eal- ime applica ions. The second scheme p oposed in his hesis
ex ac s spa ial in o ma ion using mo phological p o iles and c ea es a new ec o o ea u es
p io o he classi ica ion. The scheme is desc ibed in Sec ion 3.3.
The classi ica ion accu acy o bo h schemes is e alua ed on eal hype spec al images,
and he esul s he eo a e compa ed o classi ica ion schemes ound in he li e a u e based on
segmen a ion and MM.
3.1.1 F amewo k o spec al classi ica ion schemes
The classi ica ion schemes o hype spec al images p ocess each pixel independen ly (pixel-
wise p ocessing) and do no ake in o accoun he spa ial in o ma ion o he neighbo hood.
Success in classi ica ion depends solely on he abili y o he classi ie o disc imina e among
pixel ec o s. Thus, he classi ie disc imina es he pixels o he image based only on he
spec al ea u es cap u ed by he hype spec al senso . One possible amewo k o spec al
classi ica ion ha we will use in his hesis is gi en in Figu e 3.1. This amewo k is based
on he spec al classi ica ion scheme p oposed by Landg ebe e al. [95], which is widely used
nowadays as he basis o hype spec al image classi ica ion.
Conside ing ha he spec al ea u es a e o en edundan , Fea u e Ex ac ion (FE) and
Fea u e Selec ion (FS) a e usually pe o med as a p ep ocessing s ep. FE is designed o e-
mo e he edundancy in oduced by he spec al co ela ion be ween bands [146], while he
main cha ac e is ics in he spec al domain a e e ained. One consequence is ha he spec-
al dimensionali y is educed. Di e en echniques ha e been in es iga ed o ex ac ing he
p incipal ea u es o u ban land co e classi ica ion o hype spec al da a using SVM-based
classi ie s [48, 31]. Sec ion 2.2.1 desc ibes he echniques used in he spec al-spa ial classi i-
ca ion schemes in es iga ed in his wo k. P incipal Componen Analysis (PCA) and Indepen-
den Componen Analysis (ICA) a e wo o he mos widely used unsupe ised echniques in
emo e sensing o educing he edundancy o he spec al bands. Howe e , he Minimum
Noise F ac ion (MNF), which ex ac s he da a so ing he componen s by signal- o-noise a-
io, pe o med be e han PCA in he analysis ca ied ou in [48]. This inding emphasizes
he idea ha emo ing noise is a good p ep ocessing op ion.
Supe ised ea u e ex ac ion echniques such as Disc iminan Analysis Fea u e Ex ac ion
(DAFE), Decision Bounda y Fea u e Ex ac ion (DBFE) and Non-pa ame ic Weigh ed Fea-
u e Ex ac ion (NWFE) ha e shown hei e ec i eness in classi ica ion o hype spec al
3.1. In oduc ion 61
Figu e 3.1: Simpli ied amewo k o spec al classi ica ion schemes inco po a ing ea u e educ ion and denoising.
da a [108, 31, 93, 96]. Kuo and Landg ebe p oposed NWFE in [93], as a me hod o im-
p o ing DAFE by exploi ing di e en weigh s on samples close o he decision bounda y.
The NWFE has been shown o pe o m be e han DAFE and DBFE in classi ica ion o hy-
pe spec al da a [96].
An au oma ic ex ac ion o ea u es using wa ele was p esen ed in [86], whe e he di-
mensionali y o he image is educed se e al imes, and hen econs uc ed by wa ele s. The
bes le el o decomposi ion is hen de e mined h ough he simila i y be ween he o iginal
pixel ec o and he ec o econs uc ed using wa ele s. In [162] se e al me hods based on
wa ele ans o ms a e de eloped o ex ac use ul ea u es o classi ica ion. The Daubechies
3 wa ele is applied o hype spec al images, and a small subse o wa ele coe icien s is hen
used o ex ac he e ec i e ea u es o classi ica ion. In he wo k published in [68] wa ele
ans o ms we e used o educe he dimension o he hype spec al images, owing o i s abili y
o de ec he local ene gy a ia ions be e han o he ans o ms.
The acquisi ion o he image usually in oduces undesi able a i ac s ha may a ec he
quali y o he spec al signa u e. The e o e, ano he p ep ocessing commonly applied a e de-
noising [164, 166] and sca e co ec ion [140]. As illus a ed in Figu e 3.1, ea u e ex ac ion
and denoising a e no mu ually exclusi e.
Finally, once he p ep ocessing has been pe o med, he classi ica ion o he hype spec al
image akes place. The esul is a hema ic map in which each pixel is labelled wi h a class ha
iden i ies he co esponding spec al signa u e. In Figu e 3.1, he esul is a classi ica ion map
whe e he labels a e iden i ied by h ee di e en colo s. The e a e a a ie y o classi ie s, such
as maximum likelihood, neu al ne wo ks, decision ees, and ke nel-based me hods. Melgani
and B uzzone [110] ha e shown ha he SVM classi ie is mo e e ec i e o emo e sensing
classi ica ion han o he con en ional non-pa ame ic classi ie s, in e ms o accu acy, com-
pu a ional ime, and s abili y o pa ame e se ing. In addi ion, he SVM classi ie has been
68 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
8-connec i i y wi h s=1. The esul is a one-band g adien image which will be segmen ed
by he CA–Wa e shed algo i hm.
3.2.2 Wa e shed ans o m based on cellula au oma a (CA-Wa e shed)
Rega ding segmen a ion, Galilée e al. [64] in oduced a pa allel algo i hm-a chi ec u e based
on asynch onous CA o compu e he wa e shed ans o m. The asynch onous beha io o his
au oma on is subjec o i s implemen a ion; i.e., he CA–Wa e shed can be synch onously o
asynch onously implemen ed. The 3–s a e cellula au oma on p oposed in [64] ollows he
Hill-Climbing algo i hm desc ibed in Sec ion 2.3.2. The main ad an age o his algo i hm
is ha minima de ec ion, labelling, and climbing he s eepes pa hs a e pe o med simul ane-
ously and locally. We now go on o desc ibe he CA–Wa e shed algo i hm, whe e each cell o
he au oma on compu es a pixel o he image. The undamen als o he wa e shed ans o m
and cellula au oma a a e desc ibed in Sec ion 2.3.2 and Sec ion 2.4, espec i ely.
Figu e 3.6 shows he 3–s a e cellula au oma on ha compu es he wa e shed ans o m
which is desc ibed he ea e . Fi s , he pixels a e sequen ially labelled. In he ini ial s a e, all
pixels compu e he se s NF(u)and N=(u)co esponding o an a bi a y lowe slope and he
neighbo s wi h he same g ey alue, espec i ely. I a pixel has no lowe slope, NF(u) = /0,
i swi ches o he minimum o pla eau (MP) s a e and i s label is ini ialized as ollows:
l(u) = min(l( )),(3.1)
Compu e and
non-minimum
MP NM
INIT
look a look a
Ex end pla eaus Hill-Climbing
Figu e 3.6: 3-s a e cellula au oma on implemen ing Hill-Climbing algo i hm [64].
3.2. Scheme based on segmen a ion: CA–WSHED–MV 69
Algo i hm 1 CA–Wa e shed algo i hm [64]
1: p ocedu e CA–WATERSHED(s a e, )
2: swi ch s a e do
3: case INIT : .Ini ialize au oma on
4: compu e N=(u),NF(u)
5: i (NF(u) = /0) hen
6: l(u)←min ∈N=(u)(l( )) .Eq. (3.1)
7: s a e(u)←“MP”
8: else
9: (u)← (NF(u)) .Eq. (3.2)
10: s a e(u)←“NM”
11: end i
12:
13: case MP : .Minimum o Pla eau
14: o each pixel ∈N=(u)do
15: i h( )<h(u) hen
16: NF(u) = { }.Eq. (3.4)
17: (u)← ( )
18: s a e(u)←“NM”
19: else
20: l(u)←min(l(u),l( )) .Eq. (3.3)
21: end i
22: end o
23:
24: case NM : .Non Minimum
25: =NF(u)
26: (u)← ( ).Eq. (3.5)
27:
28: end swi ch
29: end p ocedu e
whe e l( )a e he labels o he pixels ∈N=(u). O he wise, he s a e o he pixel swi ches
o non-minimum (NM) and NF(u)poin s o he climbing di ec ion. The g ey alue and he
label o he pixel a e modi ied as ollows:
(u) = NF(u),(3.2)
whe e (u)is he pai h(u),l(u),h(u)is he g ey alue o he pixel uand l(u)i s label.
Once he pixel has been ini ialized, he upda e s age begins. This is an i e a i e ask ha
p ocesses he MP and NM s a es. A pixel in MP s a e wai s o da a om any neighbo
∈N=(u), and, depending on he g ey alue o he neighbo , wo cases a e conside ed. I
he alue o he neighbo is equal o o g ea e han i s cu en alue, he label o he pixel is
70 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
upda ed as:
l(u) = min(l(u),l( )) i h( )≥h(u).(3.3)
O he wise, he pixel belongs o he lowe bo de o he pla eau and i s s a e swi ches o NM
as ollows:
NF(u) = ,
(u) = ( ),
s a e =NM,
i h( )<h(u).(3.4)
On he o he hand, a pixel in NM s a e emains in ha s a e and wai s o da a om he
neighbo NF(u), upda ing i s da a as ollows:
(u) = (NF(u)).(3.5)
This algo i hm is non-de e minis ic and may lead o di e en segmen a ion esul s. A
o mal p oo o co ec ness and con e gence owa ds a wa e shed segmen a ion using a ma h-
ema ical model o da a p opaga ion in a g aph is p esen ed in [64]. The pseudocode o his
algo i hm is lis ed in Algo i hm 1 and Figu e 3.7 shows a guided example o he e olu ion
(a) (b)
(c) (d)
(e) ( )
Figu e 3.7: CA–Wa e shed based on Hill-Climbing algo i hm. Example o 1D image ep esen ed as a e ain wi h
dashed lines and as g ey alues wi h he squa es: a) pixels a e sequen ially labelled and s a es a e
ini ialized, b) MP upda ing s age whe e wo pixels change hei s a e o NM c) o ) he au oma on
e ol es only wi h he NM ules.
3.2. Scheme based on segmen a ion: CA–WSHED–MV 71
o he CA–Wa e shed on a 1D image, ep esen ing he g ey alues wi h he squa es and he
e ain wi h dashed lines. The au oma on ini ializa ion is shown in Figu e 3.7(a). The i s up-
da ing s ep, Figu e 3.7(b) and Figu e 3.7(c), illus a es he MP and NM s a es, espec i ely. I
can be obse ed in Figu e 3.7(b) ha wo pixels change hei s a e om MP o NM as hey be-
long o he lowe bo de o he inne pla eau. In he successi e upda ing s eps, Figu e 3.7(d) o
Figu e 3.7( ) he au oma on e ol es only wi h he NM ules. The labels a e p opaga ed om
he minimum climbing up he hills, looding he e ain.
3.2.3 Resul s
In his sec ion we conduc an analysis1. o he p oposed CA–WSHED–MV scheme in e ms
o O e all Accu acy (OA), A e age Accu acy (AA) and he kappa coe icien o ag eemen
(k). These c i e ia a e compu ed om he con usion ma ix.
The RCMG is compu ed using 8-connec i i y and he pai s o pixel ec o s emo ed is
s=1, (see Sec ion 2.2.2 and Sec ion 3.2.1 o de ails on he obus ness o his mo phological
g adien ). The CA–Wa e shed is con igu ed o use 8-connec i i y as well.
Gi en ha he classi ica ion esul s depend on he se o aining samples and hei dis i-
bu ion wi hin he hype spec al image [39], he esul s a e ob ained execu ing he classi ica ion
10 imes wi h di e en se s o aining samples each ime. Since he aining samples we e
andomly selec ed, he esul s we e calcula ed as he a e age o he 10 di e en alues ob-
ained o each execu ion. The hype spec al emo e sensing scenes used in he expe imen s
a e wo u ban a eas (Pa ia Uni e si y and Pa ia Ci y da ase s) aken by he ROSIS-03 hy-
pe spec al senso and one hype spec al image o a c op a ea (Indian Pines da ase ) aken by
he AVIRIS senso . These da ase s a e desc ibed in Sec ion 2.9.3, including he numbe o
a ailable samples.
The numbe o aining samples o each scene is chosen as in [155, 121, 54] o com-
pa e ou scheme on equal e ms. In o de o ob ain a eliable e alua ion o he esul s, he
accu acies a e calcula ed excluding he samples used o aining.
1Pa o hese esul s ha e been published in P. Quesada-Ba iuso, F. A güello, and D. B. He as, “E icien seg-
men a ion o hype spec al images on commodi y GPUs,” in 16 h In e na ional Con e ence on Knowledge-Based
and In elligen In o ma ion & Enginee ing Sys em, ol. 243, pp. 2130–2139, 2012. And P. Quesada-Ba iuso, F.
A güello, and D. B. He as, “Compu ing e icien ly spec al-spa ial classi ica ion o hype spec al images on commod-
i y gpus,” in Recen Ad ances in Knowledge-based Pa adigms and Applica ions (J. W. Tweedale and L. C. Jain, eds.),
ol. 234 o Ad ances in In elligen Sys ems and Compu ing, Ch. 2, pp. 19–42, Sp inge In e na ional Publishing,
2014.
72 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
Pa ia Uni e si y Pa ia Ci y Indian Pines
C128 128 1024
γ0.125 0.125 0.5
Table 3.1: Bes pa ame e s (C,γ) o he SVM de e mined o each hype spec al image in he ange C=[1, 4, 16,
64, 128, 512, 1024], γ=[0.5, 0.25, 0.125, 0.0625] by 5– old c oss- alida ion.
The whole p ocess is compu ed in CPU and he classi ica ion is ca ied ou using he
LIBSVM lib a y [35] wi h he RBF ke nel. The pa ame e s (C,γ) o aining he SVM a e
de e mined o each hype spec al image in he ange C=[1, 4, 16, 64, 128, 512, 1024], γ=
[0.5, 0.25, 0.125, 0.0625] by 5– old c oss- alida ion, as explained in Sec ion 2.7. Fo each
one o he hype spec al images unde s udy, a andom aining se o he a ailable samples is
used o ind he bes pa ame e s o he SVM, which a e summa ized in Table 3.1.
The classi ica ion esul s a e compa ed o hose ob ained by he pixel-wise SVM clas-
si ie and o he spec al-spa ial classi ica ion schemes based on segmen a ion and SVM, he
esul s o which a e a ailable in he li e a u e: SVM+EM (PR) [154], SVM+ISODATA [154],
SVM+ ISODATA (PR) [154], and HSeg+MV [158]. These schemes a e based on clus e ing
and egion g owing segmen a ion echniques. The HSeg+MV scheme is based on he HSEG
algo i hm p oposed in [161]. A desc ip ion o hese segmen a ion echniques was p esen ed
in Sec ion 2.3. The schemes ma ked wi h PR also include an addi ional pos egula iza ion
as desc ibed in he p e ious Sec ion. The segmen a ion map ob ained by hese schemes is
combined wi h he hema ic map p oduced by he SVM using he majo i y o ing da a usion.
These segmen a ion echniques a e also desc ibed in Sec ion 2.3.
Fo he Pa ia Ci y da ase he e a e no published esul s o spec al-spa ial classi ica ion
schemes based on segmen a ion2, so we ha e p oduced addi ional esul s o his da ase by
using wo segmen a ion algo i hms based on clus e ing. The i s classi ica ion scheme is
based on k-means (k-means–MV) and he second one is based on Quick-Shi [163] (QS–
MV). Bo h schemes combine he spec al and spa ial in o ma ion by majo i y o e.
Uni e si y o Pa ia da ase
The Uni e si y o Pa ia da ase is a mode a ely dense u ban a ea, wi h some buildings and
la ge meadows and high spa ial esolu ion (1.3 m). Nine classes o in e es a e a ailable o
2Pa ial esul o his da ase we e ound in [21] bu using a subse o 900×300 pixels.
3.2. Scheme based on segmen a ion: CA–WSHED–MV 73
SVM SVM+EM SVM+ISODATA Hseg+MV CA–WSHED–MV
[158] (PR) [154] (PR) [154] [158]
1-Asphal 84.93 93.45 94.40 94.77 95.42
2-Meadows 79.79 93.78 87.45 89.32 95.51
3-G a el 67.16 82.53 61.32 96.14 87.01
4-T ees 97.77 99.38 98.63 98.08 95.93
5-Me al shee s 99.46 100 99.91 99.82 99.72
6-Ba e Soil 92.83 97.38 97.88 99.76 97.26
7-Bi umen 90.42 94.19 100 100 98.97
8-B icks 92.78 98.31 99.02 99.29 98.51
9-Shadows 98.11 97.86 97.86 96.48 100
OA 81.01 94.64 91.20 93.85 95.88
AA 88.25 95.21 92.94 97.07 96.48
k0.758 0.929 0.884 0.919 0.944
Table 3.2: Classi ica ion esul s o he CA–WSHED–MV scheme on he Uni e si y o Pa ia da ase and compa ed
o SVM, SVM+EM (PR), SVM+ISODATA (PR), and Hseg+MV. Bes esul s a e indica ed in bold.
his scene. The numbe o aining samples used in he expe imen s was aken om [54], as
desc ibed in Sec ion 2.9.3, Table 2.6. We ecall ha he numbe o aining samples is no
included in he es se .
Table 3.2 shows he name o he classes and gi es he classi ica ion accu acies ob ained
by he pixel-wise SVM classi ie , and di e en segmen a ion schemes based on clus e ing and
pos - egula iza ion SVM+EM (PR) and SVM+ISODATA (PR), and based on Hie a chical
Image Segmen a ion Hseg+MV. Bes esul s a e indica ed in bold. Figu e 3.8 shows om le
o igh , he hema ic map p oduced by he pixel-wise SVM classi ie , he RCMG, he CA–
Wa e shed segmen a ion map wi h wa e shed lines imposed o isualiza ion, and he inal
classi ica ion map p oduced o he CA–WSHED–MV scheme.
As can be seen om Table 3.2, he spec al-spa ial classi ica ion schemes ha e highe ac-
cu acies as compa ed o he esul s ob ained by he pixel-wise SVM. The bes OA is achie ed
by he p oposed CA–WSHED–MV scheme. This scheme imp o es he OA in 14.87% and
he AA in 8.23% as compa ed o he classi ica ion by he pixel-wise SVM. The Hseg+MV
scheme has he bes AA, showing a good consis ency in he class-speci ic esul s, which we e
imp o ed o almos all he classes, excep o he shadows class. Howe e , he p oposed
scheme imp o ed all he class-speci ic accu acies, including he shadows class up o 100%.
This is an ou s anding esul because he accu acies in he six h column in Table 3.2, co e-
sponding o he p oposed scheme, a e calcula ed as he a e age o e 10 di e en classi ica ion
wi h di e en se s o aining and es samples.
74 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
Pa ia Ci y da ase
The Pa ia Ci y da ase is a dense u ban a ea, wi h many buildings and a la ge i e in he
op- igh co ne o he scene. The nine classes o in e es , which a e a ailable o his da ase
a e shown in Table 3.3. The numbe o samples used in he expe imen s is de ailed in Sec-
ion 2.9.3, Table 2.6. Table 3.3 shows he classi ica ion accu acies ob ained by he pixel-wise
SVM classi ie . O he schemes based in segmen a ion applied o his da ase in he same ex-
pe imen al condi ions we e no ound in he li e a u e. K. Be na d e al. [21] published he
esul s o hei spec al-spa ial classi ica ion scheme based on a s ochas ic minimum span-
ning o es app oach. Thei scheme p oduces a se o segmen a ion maps gene a ing andom
ma ke s om he SVM hema ic map, which a e agg ega ed by a MV. Howe e , he Pa ia
Ci y da ase used in [21] is a subse o 900×300 pixels, so i is no included in he analysis
because he numbe o es samples would no be he same. In o de o ob ain a eliable e al-
ua ion o he p oposed scheme, we ha e added he esul s o a pa i ional clus e ing app oach
by k-means (k-means–MV) gene a ed by us.
We ha e also used a Quick Shi (QS) segmen a ion echnique [163] o c ea e a second
clus e ing-based scheme (QS–MV) o compa ison. These schemes a e simila o he one
p oposed by Ta abalka e al. [154] bu wi hou pos - egula iza ion. Figu e 3.9 shows om
le o igh he hema ic map p oduced by he pixel-wise SVM classi ie , he RCMG, he
CA–Wa e shed segmen a ion map wi h wa e shed lines imposed o isualiza ion, and he
inal classi ica ion map p oduced o he p oposed CA–WSHED–MV scheme.
SVM k-means–MV QS–MV CA–WSHED–MV
[58]
1-Wa e 99.1 99.99 99.97 100
2-T ees 90.8 92.84 96.29 95.84
3-Meadow 97.4 63.25 96.89 98.33
4-B ick 87.5 97.49 98.65 98.47
5-Ba e Soil 94.6 94.49 94.79 94.76
6-Asphal 96.4 97.85 94.59 99.09
7-Bi umen 96.5 92.65 96.69 95.22
8-Tile 99.5 98.88 99.36 99.80
9-Shadows 100 95.53 94.58 100
OA 98.1 97.93 98.76 99.20
AA 95.1 92.56 96.84 97.94
k0.97 0.970 0.982 0.988
Table 3.3: Classi ica ion esul s o he CA–WSHED–MV scheme on he Pa ia Ci y da ase and compa ed o SVM,
k-means–MV and QS–MV. Bes esul s a e indica ed in bold.
3.2. Scheme based on segmen a ion: CA–WSHED–MV 75
Table 3.3 gi es he classi ica ion accu acies ob ained by he pixel-wise SVM classi ie ,
and he segmen a ion schemes based on k-means and QS, as well as he p oposed scheme.
Resul s o he pixel-wise SVM classi ie a e aken om [58]. As can be seen om Table 3.3,
all he spec al-spa ial classi ica ion accu acies a e highe as compa ed o he SVM pixel-wise
classi ie , despi e he OA ob ained as basis o compa ison is ai ly high (98.1%). The bes
OA is achie ed when using he spec al-spa ial classi ica ion scheme based on segmen a ion
by he CA–Wa e shed algo i hm. Wi h he p oposed scheme, he OA is imp o ed by 1.1%
and he AA is imp o ed by 2.87% compa ed o he pixel-wise SVM classi ica ion. The k-
means–MV scheme ob ains wo se esul s mainly because he class-speci ic accu acy o he
class meadows is only o 63.25, which is 35.15% less han he base o compa ison. The
QS–MV shows a good egula i y in he class speci ic accu acies wi h an AA o 96.84% bu
he CA–WSHED–MV scheme is mo e egula among he di e en classes (AA =97.94%).
Indian Pines da ase
The Indian Pines da ase has a low spa ial esolu ion (20 m/pixel) and simila ag icul u al
and o es ed egions. Six een classes o in e es a e a ailable in he e e ence map. The o al
numbe o samples is p esen ed in Sec ion 2.9.3, Table 2.7. The numbe o samples used o
aining he SVM is andomly aken om he e e ence map as 10% o he a ailable da a as
in [154, 58].
Table 3.4 gi es he classi ica ion accu acies ob ained by he pixel-wise SVM classi ie ,
he segmen a ion scheme based on ISODATA [154] and he segmen a ion scheme based on
hie a chical image segmen a ion (HSeg+MV) [58]. Bes esul s a e indica ed in bold. Figu e
3.8 shows om le o igh he hema ic map p oduced by he pixel-wise SVM classi ie , he
RCMG, he CA–Wa e shed segmen a ion map wi h wa e shed lines imposed o isualiza ion,
and he inal classi ica ion map p oduced o he CA–WSHED–MV scheme.
The Hseg+MV scheme ob ained he bes OA (90.8%), AA (94.0%) and kcoe icien
(0.90%) o his scene, as shown in Table 3.4. The p oposed scheme has he nex highes
AA (91.20%) showing also good egula i y in he class speci ic esul s. The SVM+ISODATA
scheme (wi h and wi hou PR) shows a less uni o m esul in he CS accu acies, leading o a
lowe AA as compa ed o he Hseg+MV and CA–WSHED–MV schemes. This is because he
al al a class and he oa s class a e poo ly classi ied by he SVM+ISODATA scheme. Mo e-
o e , he pos - egula iza ion ( ou h column in Table 3.4) educes he accu acy o hese wo
classes e en u he .
76 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
SVM SVM+ISODATA SVM+ISODATA Hseg+MV CA–WSHED–MV
[154] [154] (PR) [154] [58]
1-Al al a 32.65 12.24 6.12 92.3 95.83
2-Co n-no ill 74.59 79.32 80.48 90.5 85.22
3-Co n-min ill 64.58 84.95 88.02 83.0 86.14
4-Co n 58.77 75.83 85.31 95.7 93.90
5-G ass/pas u e 87.05 93.08 93.75 94.4 96.26
6-G ass- ees 92.72 94.80 96.88 97.6 97.27
7-G ass/mowed 29.17 91.67 91.67 100 100
8-Hay-wind owed 96.37 97.51 97.51 99.5 99.38
9-Oa s 22.22 16.67 11.11 100 65.55
10-Soybean-no ill 69.76 83.85 84.19 92.1 90.43
11-Soybean-min ill 79.21 93.16 95.77 84.1 75.28
12-Soybean-clean 75.41 85.17 89.87 95.4 95.19
13-Whea 90.58 93.19 98.43 98.2 99.57
14-Woods 91.07 97.17 97.85 98.6 93.23
15-Bld-G s-T s-D s 65.50 79.53 85.38 82.1 92.28
16-S one-S eel 84.88 86.05 87.21 100 93.64
OA 78.76 88.53 90.64 90.8 87.95
AA 69.66 79.01 80.60 94.0 91.20
k0.757 0.869 0.893 0.90 0.864
Table 3.4: Classi ica ion esul s o he CA–WSHED–MV scheme on he Indian Pines da ase and compa ed o
SVM, SVM+ISODATA, SVM+ISODATA (PR), and Hseg+MV. Bes esul s a e indica ed in bold.
3.2.4 Final discussion
In his sec ion we ha e desc ibed and analyzed he p oposed spec al-spa ial n-dimensional
image classi ica ion scheme based on segmen a ion and Majo i y Vo e (MV): CA–WSHED–
MV. The scheme educes he dimensionali y o he hype spec al image compu ing a Robus
Colo Mo phological G adien (RCMG), and hen inco po a es he spa ial in o ma ion by
a wa e shed ans o m based on cellula au oma a (CA-Wa e shed). The classi ica ion was
ca ied ou by SVM combining he spec al and spa ial esul s wi h a MV be ween he hema ic
map p oduced by he SVM and he segmen a ion map c ea ed by he CA–Wa e shed. This
scheme was o iginally p oposed in [155] bu he wa e shed algo i hm used in ou scheme
has he ad an age ha i does no c ea e he wa e shed lines, elimina ing he need o a pos -
p ocessing o he segmen a ion map o assign a egion o he pixel in he wa e shed lines.
The classi ica ion accu acy o he CA–WSHED–MV scheme was p o en, p oducing good
esul s on wo u ban a eas acqui ed by he ROSIS-03 senso (Uni e si y o Pa ia and Pa ia
Ci y da ase s), and one mixed ag icul u al and o es ed scene (Indian Pines) om he AVIRIS
senso . The classi ica ion accu acies we e compa ed o spec al-spa ial classi ica ion schemes
3.2. Scheme based on segmen a ion: CA–WSHED–MV 77
ound in he li e a u e based on he same amewo k (segmen a ion + majo i y o e): SVM+EM,
SVM+EM (PR), SVM+ISODATA, SVM+ISODATA (PR) and Hseg+MV. In addi ion, o he
segmen a ion echniques such as k-means and quick-shi (QS) we e used o ob ain a eliable
e alua ion o he p oposed scheme in he cases whe e he same spec al-spa ial amewo k
was no ound in he li e a u e o compa ison.
Expe imen al esul s ha e shown ha he p oposed scheme based on CA–Wa e shed im-
p o es he classi ica ion accu acies and pe o ms be e han o he segmen a ion-based schemes
in u ban a eas. By including spa ial in o ma ion om he closes neighbo s, h ough a ixed
o an adap i e pos - egula iza ion, small spa ial s uc u es may disappea being assimila ed
by la ge s uc u es [155]. Howe e , he CA–WSHED–MV scheme has shown o be obus
o his d awback, showing a good consis ency in he class-speci ic accu acies. In he hema ic
maps p oduced by he p oposed scheme, see Figu e 3.8(d), Figu e 3.9(d), and Figu e 3.10(d),
he spa ial s uc u es a e mo e homogeneous as compa ed o he SVM pixel-wise hema ic
map.
84 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
h g1g2
0.14301535070442 -0.01850334430500 -0.04603639605741
0.51743439976158 -0.06694572860103 -0.16656124565526
0.63958409200212 -0.07389654873135 0.00312998080994
0.24429938448107 0.00042268944277 0.67756935957555
-0.07549266151999 0.58114390323763 -0.46810169867282
-0.05462700305610 -0.42222097104302 0
Table 3.6: Se o il e s used by he 2D-DWT o denoising [148].
3.3.4 Resul s
In his sec ion he WT–EMP scheme p oposed o e icien spec al-spa ial classi ica ion o
hype spec al images is e alua ed in e ms o O e all Accu acy (OA), A e age Accu acy (AA)
and kcoe icien , which a e compu ed om he con usion ma ix3.
The scheme is c ea ed by applying he Cohen-Daubechies-Feau eau 9/7 wa ele (CDF97)
wa ele decomposi ion se e al imes in he spec al domain. The numbe o le els o de-
composi ion is pe o med o a ixed le el o p oduce always 4-band coe icien s. F om he
emaining 4-band coe icien s, he EMP is c ea ed applying 4 openings and 4 closings by
econs uc ion, using a disk o adius o inc easing size ∈[1,3,5,7]. Thus, he size o he
EMP is 36 (2n+1×4 band-coe icien s), independen ly o he size o he hype spec al da a.
See Sec ion 3.3.2 o mo e de ails. Fo image denoising, ou le els o he Double-Densi y
DWT a e applied o he hype spec al da a as desc ibed in Sec ion 3.3.3. The bes h eshold
is ound expe imen ally o each da ase . The denoised da a and he EMP a e combined ia
s ack ec o s (see Sec ion 3.1.3). The whole p ocess is compu ed in MATLAB4.
The hype spec al emo e sensing scenes used in he expe imen s a e wo u ban a eas
(Pa ia Uni e si y and Pa ia Ci y da ase s) aken by he ROSIS-03 hype spec al senso and
one hype spec al image o a c op a ea (Indian Pines da ase ) aken by he AVIRIS senso . The
numbe o aining samples o each scene a e selec ed as in [54, 41] o compa e ou scheme
on equal e ms (see Sec ion 2.9.3, Table 2.6 and 2.7). In o de o ob ain a eliable e alua ion
o he esul s, he accu acies a e calcula ed excluding he samples used o aining.
3Pa o hese esul s ha e been published in P. Quesada-Ba iuso, F. A güello, and D. B. He as, “Spec al-
spa ial classi ica ion o hype spec al images using wa ele s and ex ended mo phological p o iles,” Selec ed Topics
in Applied Ea h Obse a ions and Remo e Sensing, IEEE Jou nal o , ol. 7, no. 4, pp. 1177–1185, 2014.
4The Double-Densi y DWT so wa e used in hese expe imen s is a ailable a [147].
3.3. Scheme based on mo phological p o iles: WT–EMP 85
Pa ia Uni e si y Pa ia Ci y Indian Pines
C128 128 1024
γ0.125 0.125 0.5
Table 3.7: Bes pa ame e s (C,γ) o he SVM de e mined o each hype spec al image in he ange C=[1, 4, 16,
64, 128, 512, 1024], γ=[0.5, 0.25, 0.125, 0.0625] by 5– old c oss- alida ion.
In his analysis he esul s a e ob ained execu ing he classi ica ion 100 imes wi h di e en
se s o aining samples each ime. Since he aining samples we e andomly selec ed, he
esul s we e calcula ed as he a e age o he 100 di e en alues ob ained o each execu ion.
The classi ica ion is ca ied ou using he LIBSVM lib a y [35] wi h he RBF ke nel. The
pa ame e s (C,γ) o aining he SVM a e de e mined by 5– old c oss- alida ion and a e
shown in Table 3.7.
We also conduc a s andalone analysis o he di e en s ages o he p oposed scheme o
asce ain whe he he EMP c ea ed using wa ele s and he con ibu ion o he denoising as a
p ep ocessing s age a e e icien . The s ages a e named:
1. WT–EMP†is he s age conside ing only he EMP c ea ed om wa ele coe icien s as
inpu o he SVM classi ie , as indica ed in he uppe b anch in Figu e 3.11.
2. WT–EMP‡is he s age conside ing only he Double-Densi y DWT applied o he hy-
pe spec al da a, see bo om b anch in Figu e 3.11.
In addi ion, we ha e e alua ed a a ian o he p oposed scheme, he eina e WT–EMP?, by
c ea ing he s ack ec o om he o iginal da a wi hou denoising and he EMP c ea ed om
wa ele coe icien s. I is simila o he scheme p oposed by Fau el e al. [54]. The di e en
s ages o he p oposed scheme a e also e alua ed sepa a ely in p esence o noise.
The classi ica ion esul s a e compa ed o hose ob ained by he pixel-wise SVM classi ie
and o he spec al-spa ial classi ica ion schemes, which esul s a e a ailable in he li e a u e
o he da ase s used in hese expe imen s: EMP-PCA [58], EMP-ICA [121], Spec-EMP [54],
WSHED+MV [58], HSeg+MV [58], DB-DB [108], EMD-DWT [68], KPCAp[108] and NW-
NW [108]. A b ie desc ip ion o hese schemes is gi en in he ollowing sec ions whe e he
men ioned schemes a e included o compa ison.
86 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
Pa ia Uni e si y da ase
The Uni e si y o Pa ia is a mode a ely dense u ban a ea wi h nine classes o in e es a ailable
in he e e ence map. This da ase has 103 spec al bands.
Fo his scene, he spec al dimensionali y is educed 6 imes by he 1D-DWT, p oducing
a EMP o 36 ea u es. I has been expe imen ally ound ha he bes pa ame e s o denoising
his hype spec al image by he Double-Densi y DWT [148] was by using a h eshold o 4.
The new pixel ec o is s acked, esul ing in 139 ea u es which a e used o classi y he image
by he SVM. Table 3.8 gi es he classi ica ion accu acies ob ained by he pixel-wise SVM
classi ie , EMP-PCA, Spec-EMP, DB-DB, EMD-DWT, WT–EMP†s age, WT–EMP?, as well
as he p oposed WT–EMP scheme. In he ollowing, hese schemes a e b ie ly desc ibed:
– EMP-PCA [58] is a spec al-spa ial classi ica ion scheme based on EMPs whe e he
mo phological p o iles a e c ea ed om he i s p incipal componen s ex ac ed by PCA.
– Spec-EMP [54] is c ea ed as he EMP-PCA scheme and s acks he o iginal spec al
in o ma ion wi hin he EMP.
– DB-DB [108] is a spec al-spa ial classi ica ion scheme based on EMAPs whe e each
a ibu e p o ile is c ea ed om he i s componen s ex ac ed by DBFE. The a ibu es con-
side ed in his scheme a e he a ea and he s anda d de ia ion. The EAPac ea ed om he
a ea and he EAPsc ea ed om he s anda d de ia ion a e conca ena ed ia s ack ec o s o
c ea e he EMAP, which is educed a second ime by DBFE.
– EMD-DWT [68] uses spa ial and spec al ea u es combining Empi ical Mode Decom-
posi ion (EMD) wi h wa ele s, in o de o gene a e he smalles se o ea u es ha leads o
he bes classi ica ion accu acy. Thus, da a usion is implici ly pe o med by a sequence o
echniques applied in he spa ial (EMD) and he spec al (DWT) domain.
The bes esul s in Table 3.8 a e indica ed in bold. All esul s a e ob ained wi h he numbe
o aining and es samples desc ibed in Sec ion 2.9.3, excep o he EMD-DWT scheme ha
conside s 1% mo e o aining samples, as epo ed in hei wo k.
By conside ing only he EMP c ea ed om he wa ele coe icien s ( ou h column in Ta-
ble 3.8) he imp o emen o he OA is 12.89%, eaching 93.9%, as compa ed o he pixel-wise
SVM. The WT–EMP†s age as compa ed o he EMP-PCA imp o es he OA in 14.8%. All
classes excep he ba e soil class a e imp o ed in his s age when compa ed o he SVM clas-
si ie , unlike he EMP-PCA, whe e nei he he g a el class and shadows class a e imp o ed
(see Table 3.8). The EMP om 1D-DWT (WT-EMP†) pe o ms be e han he EMP om
PCA (EMP-PCA) in e ms o classi ica ion accu acy o his da ase .
3.3. Scheme based on mo phological p o iles: WT–EMP 87
SVM EMP-PCA WT-EMP†DB-DB spec-EMP WT-EMP?EMD-DWT WT-EMP
[54] [58] [114] [54] [68]
1-Asphal 84.5 94.5 97.6 95.43 95.3 98.0 — 98.8
2-Meadows 66.2 72.8 91.6 95.88 73.5 97.2 — 98.8
3-G a el 72.0 53.2 95.7 100 65.9 96.2 — 98.8
4-T ees 98.0 98.9 98.9 90.94 99.2 99.0 — 99.2
5-Me al shee s 99.5 99.5 99.7 100 99.5 99.7 — 99.9
6-Ba e Soil 93.1 58.1 89.9 98.41 84.1 96.3 — 98.5
7-Bi umen 91.2 96.1 96.9 99.18 97.2 97.5 — 99.0
8-B icks 92.3 95.3 96.1 98.65 96.1 96.7 — 98.0
9-Shadows 96.6 91.2 99.9 99.96 93.5 99.9 —99.9
OA 79.5 79.1 93.9 97.89 83.5 97.4 99.0 98.8
AA 88.1 84.3 96.3 97.60 89.4 97.8 — 99.0
κ0.74 0.73 0.91 0.972 0.79 0.96 0.97 0.98
Table 3.8: Classi ica ion esul s o he WT–EMP scheme on he Uni e si y o Pa ia scene compa ed o SVM, EMP-PCA, EMAP, spec-EMP, EMD-DWT.
No e ha in EMD-DWT 1% mo e aining samples a e used in he classi ica ion. The bes accu acies a e indica ed in bold. The †indica es ha
he EMP is used as he only inpu o he SVM and ? ha he s acked ec o is buil om he o iginal da a and he EMP.
88 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
(a) (b) (c)
Figu e 3.12: WT–EMP on he Uni e si y o Pa ia da ase : (a) ue colo ep esen a ion, (b) SVM classi ica ion
map, and (c) WT–EMP classi ica ion map.
The esul s o he DB-DB, which uses di e en a ibu es o c ea e an ex ended mul i-
a ibu e p o ile, a e highe , ou pe o ming he a o emen ioned schemes. Two classes, g a el
and me al shee s, ha e a class-speci ic accu acy o 100%. Howe e , he accu acy o he ees
class alls 7% as compa ed o he pixel-wise SVM classi ie .
By inco po a ing he o iginal spec al da a in o he EMP ia s ack ec o s (se en h column
in he able), all he class-speci ic accu acies a e imp o ed. This is he same app oach as
he one p oposed in [54] (Spec-EMP) bu using 1D-DWT ins ead o PCA o compu e he
EMP. The WT-EMP?imp o es he OA 3.5% and he AA 1.5% as compa ed o he WT-
EMP†s age. These esul s a e be e no only o e he image as a whole, bu also o e each
class-speci ic accu acy. This indica es ha he classi ica ion using he EMP c ea ed om he
ea u es ex ac ed by wa ele s pe o ms be e when he spec al in o ma ion is inco po a ed
o he scheme.
The OA o 97.4% ob ained by he WT-EMP?app oach is high, bu he e is oom o im-
p o emen by applying he 2D-DWT denoising o each hype spec al band. I he o iginal
spec al da a i denoised be o e combining he esul s wi h he EMP (nin h column in Ta-
3.3. Scheme based on mo phological p o iles: WT–EMP 89
ble 3.8), he bes esul in e ms o class-speci ic accu acy, AA (99.0%) and kcoe icien
(0.98) a e ob ained. These esul co espond o he p oposed scheme. In he WT–EMP
scheme, all he class-speci ic accu acies a e among he highes , pa icula ly o he asphal ,
meadows, ees and ba e soil classes, whe e some o he o he schemes p esen ed a numbe o
di icul ies in imp o ing hose classes. Compa ed o he EMD-DWT scheme, he OA alues
a e close in bo h schemes (0.2% highe o he EMD-DWT scheme) wi h he ad an age ha
he WT-EMP is compu a ionally less cos ly.
Figu e 3.12 shows om le o igh , he ue colo ep esen a ion, he SVM classi ica ion
map, and he WT–EMP classi ica ion map.
Pa ia Ci y da ase
The Pa ia Ci y da ase is a dense u ban a ea wi h 102 spec al bands and nine classes o
in e es . Fo his image, a h eshold o 4 o denoising he hype spec al is used, and he
spec al dimensionali y is educed 5 imes by he 1D-DWT. Thus, he size o he pixel ec o s
is 138 (123 spec al bands + 36 ea u es om he EMP).
The numbe o aining samples used in he expe imen s is desc ibed in Sec ion 2.9.3,
Table 2.6. The classi ica ion accu acies ob ained by he p opose scheme, he EMP-ICA [121],
he Spec-EMP [54], as well as WT–EMP†s age and he WT–EMP?app oach a e gi en in
Table 3.9. The accu acy o he pixel-wise SVM is included as a basis o compa ison. The
EMP-ICA is a spec al-spa ial classi ica ion scheme based on EMPs whe e he mo phological
p o iles a e c ea ed om he i s p incipal componen s ex ac ed by ICA. In he Spec-EMP
scheme, he mo phological p o iles a e c ea ed om PCA and hen hey a e s acked o he
o iginal spec al in o ma ion.
I can be obse ed in he able ha he base classi ica ion accu acy is al eady ai ly high
(97.7%) using only he spec al in o ma ion. The mos signi ican imp o emen s a e achie ed
by he WT–EMP scheme. Compa ing he hi d and ou h columns ( wo simila app oaches), 7
om he 9 classes a e be e classi ied wi h he WT–EMP†s age as compa ed o he EMP-ICA
scheme. The same happens when analyzing he esul s ob ained by he WT–EMP?app oach,
whe e all he class speci ic accu acies a e imp o ed. This indica es ha he EMP c ea ed om
he wa ele coe icien s is wo king p ope ly and i is he ac o ha con ibu es mos o he
scheme.
The bes OA (99.7%), AA (99.3%), and kcoe icien (0.99) a e ob ained o he p oposed
scheme, when he denoised da a a e s acked wi h he EMP c ea ed om wa ele s. Figu e
90 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
SVM EMP-ICA WT-EMP†spec-EMP WT-EMP?WT-EMP
[54] [121] [54]
1-Wa e 98.3 99.5 99.9 98.6 99.9 99.9
2-T ees 91.2 91.7 95.7 93.5 97.8 97.4
3-Meadow 96.8 85.3 98.0 95.9 98.5 99.1
4-B icks 88.4 99.2 99.7 98.8 99.7 99.8
5-B. Soil 97.0 98.4 99.8 99.4 99.8 99.9
6-Asphal 96.3 98.6 98.7 98.4 99.0 99.5
7-Bi umen 96.0 98.1 97.1 98.2 98.3 98.5
8-Tiles 99.4 99.8 99.8 99.8 99.8 99.9
9-Shadows 99.9 99.2 99.9 99.9 99.9 100
OA 97.7 98.8 99.5 99.7 99.7 99.7
AA 95.6 96.6 98.8 98.1 99.2 99.3
κ0.96 – 0.99 0.98 0.99 0.99
Table 3.9: Classi ica ion esul s o he WT-EMP scheme on he Pa ia Ci y compa ed o SVM, EMP-ICA, and
spec-EMP. The bes accu acies a e indica ed in bold. The †indica es ha he EMP is used as he only
inpu o he SVM and ? ha he s acked ec o is buil om he o iginal da a and he EMP.
(a) (b) (c)
Figu e 3.13: WT–EMP on he Pa ia Ci y da ase : (a) ue colo ep esen a ion, (b) spec al classi ica ion map wi h
SVM, (c) WT-EMP classi ica ion map.
3.13 shows om le o igh he ue colo ep esen a ion, he spec al classi ica ion map wi h
SVM and he WT-EMP classi ica ion map.
3.3. Scheme based on mo phological p o iles: WT–EMP 91
Indian Pines da ase
The hi d scena io used in he expe imen s is he Indian Pines da ase , wi h he six een classes
ex ac ed om i s e e ence map. This da ase has 220 spec al bands. A h eshold o 0.01
o denoising he hype spec al da a ob ained he bes classi ica ion accu acy in his image.
The spec al dimensionali y is educed 6 imes by he 1D-DWT, c ea ing s ack ec o s o 256
ea u es (220 spec al bands + 36 ea u es om he EMP). The numbe o samples used o
aining he SVM is he same as in [58, 108]. The aining samples a e andomly aken om
he e e ence map, desc ibed in Sec ion 2.9.3.
Table 3.10 gi es he classi ica ion accu acies ob ained by he pixel-wise SVM classi ie ,
by he WT–EMP scheme, and wo MM-based schemes, KPCApand NW-NW [108]. The bes
esul s a e indica ed in bold.
The MM-based schemes a e based on EMAPs, c ea ing he p o ile using he a ea and
s anda d de ia ion a ibu es. The mo phological p o iles a e c ea ed on he p incipal compo-
nen s ex ac ed by ke nel-PCA (KPCAp) and NWFE (NW-NW) ea u e ex ac ion echniques,
espec i ely. The i s has 325 ea u es ha a e used as inpu o he SVM classi ie , and he
NW-NW uses a ea u e ex ac ion echnique a second ime o educe he EMAP o 30 ea u es.
Two segmen a ion-based schemes, WSHED+MV and HSeg+MV, a e also included o a
b oade compa ison. The esul s o hese wo schemes a e aken om [58] and no om [155],
as he esul s p esen ed by Fau el we e p oduced in [58] by he same numbe o aining
samples used in his expe imen .
(a) (b) (c)
Figu e 3.14: WT–EMP on he Indian Pines da ase : (a) ue colo ep esen a ion, (b) spec al classi ica ion map
wi h SVM, (c) WT-EMP classi ica ion map.
92 Chap e 3. Spec al-spa ial classi ica ion schemes based on segmen a ion and MM
SVM WSHED+MV Hseg+MV KPCApNW-NW WT–EMP
[58] [58] [58] [108] [108]
1-Al al a 74.4 94.9 92.3 94.87 94.87 91.5
2-Co n-no ill 78.2 94.2 90.5 71.41 90.24 83.7
3-Co n-min ill 69.6 78.1 83.0 92.73 98.85 85.7
4-Co n 91.9 88.6 95.7 96.20 97.28 94.6
5-G ass-pas u e 92.2 95.1 94.4 93.96 95.52 92.3
6-G ass- ees 91.7 98.8 97.6 98.42 99.56 97.2
7-G ass-pas u e-mowed 100 100 100 90.91 100 100
8-Hay-wind owed 97.7 99.5 99.5 98.63 99.54 99.1
9-Oa s 100 100 100 100 100 100
10-Soybean-no ill 82.0 96.3 92.1 87.39 86.27 84.4
11-Soybean-min ill 58.0 68.8 84.1 87.84 94.58 74.9
12-Soybean-clean 87.9 90.8 95.4 96.35 93.61 84.6
13-Whea 98.8 99.4 98.2 99.38 99.38 99.2
14-Woods 93.0 99.7 98.6 95.90 92.36 87.7
15-Bldg-G ass-T ees-D i es 61.5 69.4 82.1 96.36 99.09 94.3
16-S one-S eel-Towe s 97.8 95.6 100 100 100 96.9
OA 78.2 86.6 90.8 90.20 94.2 86.6
AA 86.9 91.6 94.0 96.64 96.3 92.3
κ0.75 0.85 0.90 0.888 0.93 0.848
Table 3.10: Classi ica ion esul s o he WT–EMP scheme on Indian Pines and compa ed o SVM, WSHED+MV, HSeg+MV, KPCAp, NW-NW. The bes
accu acies a e indica ed in bold.
3.3. Scheme based on mo phological p o iles: WT–EMP 93
As can be seen om Table 3.10, he bes OA (94.2%) and k alue (0.93) a e achie ed
by he NW-NW scheme, and he bes AA (96.64%) o he KPCApapp oach, bo h based on
a ibu e p o iles. Ou p oposed scheme gi es an OA simila o he WSHED+MV scheme
(86.6%), showing di icul ies in classi ying an image wi h low spa ial esolu ion. Howe e ,
he CS o he g ass-pas u e-mowed and oa s classes a e among he bes , wi h a alue o 100%.
E en hough, he EMP is conside ed an e ec i e app oach o combining spec al and spa ial
in o ma ion [58, 108], he EMAP gi es mo e accu a e esul s in classi ying he Indian Pines
da ase .
Figu e 3.14, shows om le o igh , he ue colo ep esen a ion o he Indian Pines
scene, he spec al hema ic map wi h SVM, and he WT-EMP hema ic map.
Expe imen al esul s in p esence o noise
This sec ion analyzes how each one o he s ages o he p oposed scheme wo ks sepa a ely
in he p esence o noise. The wo s ages a e WT–EMP‡, in which he Double-Densi y DWT
is applied o he hype spec al da a, and he WT–EMP†s age, which only conside s he EMP
c ea ed om he wa ele coe icien s as inpu o he SVM classi ie . The expe imen s we e
ca ied ou wi h he same con igu a ion as desc ibed a he beginning o Sec ion 3.3.4.
The Uni e si y o Pa ia da ase was co up ed by addi i e whi e Gaussian noise (AWGN)
[98] wi h a peak signal- o-noise a io (PSNR) o 10, 16 and 20 dB.
SVM WT–EMP‡WT-EMP†WT-EMP
1-Asphal 56.5 90.2 89.4 97.6
2-Meadows 40.2 99.1 85.8 97.8
3-G a el 15.9 99.6 83.9 98.4
4-T ees 78.5 80.5 91.9 96.4
5-Me al 91.9 99.8 99.5 99.6
6-Ba e Soil 33.7 99.9 90.8 99.2
7-Bi umen 16.3 99.9 89.5 98.9
8-B icks 49.2 98.2 85.8 97.4
9-Shadows 90.8 67.2 98.6 99.0
OA 45.9 96.0 88.0 97.3
AA 52.6 92.7 90.6 98.3
κ0.33 0.94 0.84 0.97
Table 3.11: Classi ica ion esul s o WT–EMP in p esence o noise o a PSNR o 10 dB. Uni e si y o Pa ia
da ase .
100 Chap e 4. Techniques and s a egies o e icien GPU compu ing
(a) (b)
Figu e 4.2: Hype spec al da a pa i ioning echniques: (a) spa ial-domain pa i ioning, (b) spec al-domain
pa i ioning.
one by e, one alue pe bi , and he RGB alues o a colo image can be packed in o h ee
by es. Thus, by packing da a he numbe o global memo y accesses is educed when da a a e
equi ed in a ke nel. In addi ion, i da a om neighbo ing pixels a e also equi ed, he global
memo y accesses a e e en mo e educed. This echnique is used in he CA–Wa e shed based
on Block–Asynch onous compu a ion.
4.1.3 Spec al and spa ial pa i ioning
In hype spec al imaging, wo ypes o da a pa i ioning echniques can be exploi ed: one in
he spec al-domain and o he in he spa ial-domain [127]. These wo da a pa i ioned s a e-
gies a e shown in Figu e 4.2 whe e he [x,y] on plane in each igu e co esponds o he i s
band o he image. In he spa ial-domain pa i ioning, he pixel ec o s a e kep as a whole,
as shown in Figu e 4.2(a). In he spec al-domain pa i ioning, he image is subdi ided in o
slices comp ising con iguous spec al bands, as shown in Figu e 4.2(b). The da a pa i ioning
app oach s ongly depends on he p ocessing echniques applied o analyze he hype spec al
image. Fo example, i all he spec al ea u es o a pixel a e equi ed a once o make a com-
pu a ion, as in he case o unmixing p ocessing, he spa ial-domain pa i ioning is desi ed,
as each pixel ec o can be assigned o a di e en block o h eads. Howe e , i he com-
pu a ion can be indi idually done in each band, as in he case o mo phological ope a ions,
4.1. In oduc ion 101
he spec al-domain pa i ioning can ake ad an age o he ine-g ained le el o pa allelism o
CUDA.
In his wo k, di e en hype spec al da a pa i ioning s a egies and h ead block a ange-
men s a e s udied in o de o e ec i ely exploi he memo y and compu ing capabili ies o he
GPU a chi ec u e.
4.1.4 Challenges o GPU compu ing
In o de o maximize he pe o mance on he GPU, di e en aspec s mus be aken in o con-
side a ion. This sec ion highligh s some key GPU pe o mance issues ha can be g ouped
in h ee main ules o GPGPU p og amming: 1) minimizing da a ans e be ween CPU
and GPU, 2) gi ing he GPU enough wo k o do, and 3) ocusing on da a euse wi hin he
GPU [53].
Mos o he impo an issues a e ela ed o an e icien use o he memo y hie a chy. Da a
mo emen om he CPU o he GPU global memo y is h ough he PCIe bus, which is e y
slow (8GB/s) in compa ison o he peak bandwid h o he global memo y (250 GB/s) and he
sha ed memo y (2.5 TB/s). The e o e, da a should be copied o he GPU once and be eused
as much as possible.
As memo y ope a ions a e execu ed pe wa p, i is impo an o known how da a a e going
o be accessed, which mainly depends on how we implemen he algo i hm. By aligning
accesses o consecu i e memo y loca ions in global memo y, we ensu e coalesced accesses
(see CUDA pa allel p og amming model in Sec ion 2.8.2), minimizing load/s o e ope a ions
in o he ewes possible memo y ansac ions. Da a in cons an memo y can be b oadcas i he
same alue is accessed by all he h eads wi hin he wa p. And ex u e memo y has special
ea u es, such as il e ing, and a dedica ed cache memo y which can imp o e pe o mance
when h eads access alues in some egula spa ial neighbo hood, o example in a 3 ×3
window. The e o e, da a may need o be ea anged o dis ibu ed in a di e en way in o de
o ob ain maximum pe o mance o he GPU memo y.
Da a packing, as desc ibed in Sec ion 4.1.2, can be used o minimize da a ans e s, and
di e en da a pa i ioning s a egies, see Sec ion 4.1.3, as well as h ead block a angemen s
can imp o e he pe o mance o he GPU.
The size o a block o h eads should be a mul iple o he wa p size (32). In mos o
he cases, i is o en necessa y o pe o m di e en ke nel launch con igu a ions ( h eads pe
block and blocks pe g id) o ind he bes one ha maximizes he de ice u iliza ion [118].
102 Chap e 4. Techniques and s a egies o e icien GPU compu ing
The limi in he ha dwa e esou ces equi ed o execu e a ke nel can be achie ed by he size
o he block, as desc ibed in Sec ion 2.9.1. The occupancy, which can be exp essed as he
numbe o concu en h eads pe SM can be used o measu e he pe o mance on he GPU.
The amoun o occupancy equi ed o each he maximum pe o mance depends on he code.
I he code is limi ed by memo y accesses, he highes numbe o concu en blocks pe SM
is desi ed in o de o hide he la ency o hose accesses.
Ins uc ions a e also execu ed pe wa p, so he 32 h eads wi hin he wa p ake he same
pa h in he code. In condi ional con ol lows, such as i /else s a emen s, i a leas one h ead
wi hin he wa p akes a di e en pa h, we ha e a wa p di e gence in he code, which po en-
ially a ec pe o mance [118]. Hence, ca e mus be aken o w i e a cohe en con ol low
code. In some cases, sequen ial code mus be ew i en o expose su icien pa allelism o
he GPU, and a i hme ic ins uc ions eo de ed and spli o balancing he wo kload among
memo y accesses and compu a ion.
Rega ding da a euse wi hin he GPU, i da a accesses ha e su icien locali y, edundan
accesses o global memo y mus be minimized by exploi ing he sha ed and he cache mem-
o ies. The main use o he sha ed memo y is o euse da a wi hin a block and sha e da a
among he h eads o he same block. This memo y is managed by he p og amme , and he
e ec i e use o his memo y can lead o speedups o 7×compa ed o global memo y imple-
men a ions [40]. This is a signi ican challenge when p og amming o he GPU as da a in
his on-chip memo y a e only sha ed o he h eads o he same block. Sha ing da a among
all he h eads mus be h ough he global memo y, coming in o play he a o emen ioned key
GPU pe o mance issues ela ed o an e icien use o he memo y hie a chy.
A omic memo y ope a ions may be necessa y o a oid ace condi ions in applica ions
whe e mul iple h eads need o access he same memo y space simul aneously o eading
and w i ing da a, and he e is no o he way o synch onizing. CUDA p o ides a omic ope a-
ions o ensu ing ha all concu en upda es o he same memo y loca ion can be pe o med
a omically, so ha all h eads can see hose upda es. Howe e , he a omic ope a ions can de-
g ade he pe o mance i many h eads y o ca y ou an a omic ope a ion on a small numbe
o memo y loca ions.
A ex ensi e ange o skills a e needed o be an e ec i e pa allel p og amme [90]. These
skills can be g ouped in o compu e a chi ec u e, p og amming models and compile s, algo-
i hm echniques and domain knowledge. The CUDA C p og amming guide [119] and he
4.2. Block–Asynch onous s a egy 103
CUDA C bes p ac ices guide [118] ha e a comp ehensi e manual and nume ous ips and key
issues o inc easing he compu a ional h oughpu o NVIDIA GPUs.
4.2 Block–Asynch onous s a egy
In his sec ion we p esen he Block–Asynch onous (BA) s a egy p oposed in his hesis o
e icien compu a ion o p oblems which equi e i e a i e compu a ion, such as he Cellula
Au oma a (CA). This me hod educes he numbe o poin s o global synch oniza ion al-
lowing e icien exploi a ion o he memo y hie a chy o he GPU. By BA compu a ion, we
mean upda ing a g oup o alues an unbounded numbe o imes wi hou a global synch o-
niza ion. Thus, each egion is upda ed asynch onously wi h espec o o he egions. Fo
example, a cellula au oma a can be pa i ioned in o di e en g oups o cells which can be
upda ed independen ly and locally. This s a egy pe ec ly ma ches he iling/g ids pa allel
pa e n desc ibed in he p eceding sec ion. This model is shown in Fig. 4.3 o a 6×6 cel-
lula au oma on. Each block ( ile) o 3 ×3 cells is upda ed an unbounded numbe o imes
(in a-block upda es) bu he alues ou side he block, co esponding o he ap on, a e kep
cons an ; i.e., equal o hei alues a he beginning o he s age. The en i e g id is upda ed
a e a global synch oniza ion, so da a a e ead a he block bounda ies (in e -block upda es),
which allows he p opaga ion o da a ac oss he blocks. The BA s a egy is also adequa e o
mul ico e a chi ec u es.
This s a egy can easily be adap ed o sol e di e en algo i hms, such as he asynch onous
cellula au oma on o compu e he wa e shed ans o m on GPU [139, 135, 138]. Ad anced
MM ope a ions can also bene i om he BA app oach, o example opening and closing by
econs uc ion and g eyscale a ibu e il e ing, as i will be shown in he nex sec ions.
The emainde o his sec ion is o ganized as ollows. Sec ion 4.2.1 p esen he CA–
Wa e shed algo i hm based on Block–Asynch onous compu a ion and i s ex ension o 3D
o olumes p ocessing. In Sec ion 4.2.2 we p esen a Block–Asynch onous algo i hm o
compu ing opening and closing by econs uc ion (BAR) on GPU [134]. In Sec ion 4.2.3
we desc ibe a new p oposal o g eyscale a ea opening and closing on GPU which can be
ex ended o o he a ibu es. Finally, he esul s a e discussed in Sec ion 4.2.4.
104 Chap e 4. Techniques and s a egies o e icien GPU compu ing
Figu e 4.3: Example o Block–Asynch onous s a egy, mapping on 6×6 CA (4-connec i i y). In a-block upda ing
(le ) and in e -block upda ing ( igh ).
4.2.1 CA–Wa e shed based on Block–Asynch onous compu a ion on
GPU
The Wa e shed T ans o m based on cellula au oma a (CA–Wa e shed) was desc ibed in Sec-
ion 3.2.2. The asynch onous beha iou o his au oma on, in oduced by Galilée e al. [64],
is subjec o i s implemen a ion. In he ollowing, we desc ibe i s he synch onous imple-
men a ion ha can be execu ed in CPU using OpenMP, as well as on GPU. The idea is gi ing
he ounda ions o unde s anding he asynch onous beha iou o he au oma on. Then, he
GPU Block–Asynch onous compu a ion o he same algo i hm is desc ibed. The algo i hm
is non-de e minis ic and may in oduce a i ac s in o he bo de o he segmen ed egions.
The e o e, we p opose an a i ac s- ee block–asynch onous GPU implemen a ion ha p o-
duces he co ec esul s by co ec ing he da a p opaga ion speed among he blocks using
wa e on echniques [112]. These implemen a ions ollow he pa allel iling/g ids pa e n in
which he g id o cells o he au oma on is pa i ioned in o egula egions ha a e assigned o
blocks o h eads o he GPU.
Finally, due he na u e o he CA, he implemen a ion can be easily ex ended o h ee
dimensions in o de o p ocess a 3D olume.
Block–Synch onous compu a ion on GPU
The CA–Wa e shed synch onous implemen a ion has wo ke nels: one o ini ializing and
ano he o upda ing he au oma on. The pseudo-code p esen ed in Figu e 4.5 shows he
4.2. Block–Asynch onous s a egy 105
Compu e and
non-minimum
MP NM
INIT
look a look a
Ex end pla eaus Hill-Climbing
Figu e 4.4: Th ee-s a e cellula au oma on implemen ing Hill-Climbing algo i hm [64].
block-synch onous compu a ion on GPU. The ke nels execu ed on GPU a e placed be ween
<> symbols. The pseudocode also includes he Tex, GM and SM ac onyms o indica e
ke nels execu ed wi h da a on ex u e, global and sha ed memo y, espec i ely. Figu e 4.4
in his page ecalls he 3–s a e cellula au oma on desc ibed in Sec ion 3.2.2 o compu e he
wa e shed ans o m. The NF(u)and he se o neighbo s wi h he same g ey alue, N=(u),
a e compu ed o each pixel in he i s ke nel (line 2 in he pseudocode). In he second
ke nel (line 4), he upda es lood each egion wi h a ep esen a i e label in an i e a i e p ocess
execu ed by he CPU wi h a global synch oniza ion a each s ep (line 5). These ke nels a e
con igu ed o wo k in ec angula h ead blocks wi h a h ead ope a ing on one pixel.
Wi h he i s ke nel, he au oma on is ini ialized acco ding o l(u) = min(l( )) and
(u) = NF(u), co esponding o Eq. (3.1) and Eq. (3.2), espec i ely (see page 68).
The g ey alues a e ead om ex u e memo y, as his ead-only memo y speeds up he ac-
Inpu : one band image Ion he global memo y o he GPU
Ou pu : segmen a ion map
1: copy inpu da a I om global o ex u e memo y
2: <ini ialize cellula au oma on> . (Tex and GM)
3: while cellula au oma on is no s able do
4: <synch onous upda ing o he au oma on> . (GM)
5: global synch oniza ion among blocks
6: end while
Tex: ex u e memo y, GM: global memo y.
Figu e 4.5: Pseudocode o CA–Wa e shed synch onous implemen a ion on GPU.
106 Chap e 4. Techniques and s a egies o e icien GPU compu ing
(a)
(b)
Figu e 4.6: Example o da a packing. (a) Da a o he au oma on packed in o 64 bi s, (b) s uc u e o he a iable
N=(u)using 4-connec i i y packed in 1 by e.
cesses o da a when hey p esen high spa ial locali y. Once all da a ha e been ini ialized,
hey a e packed in o 64 bi s be o e being ans e ed o global memo y, wi h he objec i e o
inc easing he da a locali y and educing numbe o global memo y accesses. The minimum
amoun o da a equi ed a e 4 by es o l(u), 1 by e o h(u), 1 by e o N=(u)and 2 by es
o NF(u). Fig. 4.6(a) shows an example o da a packing o one pixel. The se N=(u)is
comp essed in 1 by e using 1 bi o each neighbo (L, R, U, D in Fig. 4.6(b)) whe e “1” means
a neighbo wi h he same g ey le el and “0” means a neighbo wi h a di e en one. The ou
leas signi ican bi s a e igno ed bu hey may be used o connec up o 8 neighbo s. I is no
necessa y o s o e he s a e o each pixel as i can be deduced om NF(u)(see Figu e 4.4).
I he lowe slope is emp y, he s a e is MP; o he wise, he s a e is NM.
A he end o he ini ializa ion s age he s a e o each pixel, a cell o he au oma on, has
swi ched o NM o MP. In o de o upda e all he pixels synch onously, we use wo 64-bi
bu e s, one inpu bu e o eading da a and one ou pu bu e o w i ing he esul s.
The upda ing s age has been implemen ed h ough a loop execu ed by he CPU (lines 3–6
in he pseudocode o he Figu e 4.5), which calls a CUDA ke nel a each s ep (line 4). The e is
one global synch oniza ion pe s ep, as indica ed in line 5, which makes he compu a ion wai
un il he GPU inishes i s cu en wo k [119]. The inpu and ou pu bu e s a e swapped be o e
he nex i e a ion. Only one lag needs o be mo ed o he CPU a each in e -block i e a ion
4.2. Block–Asynch onous s a egy 107
Inpu : cellula au oma on packed in 64 bi s
Ou pu : cellula au oma on upda ed
1: load and unpack da a om global memo y o egis e s .inpu bu e
2: upda es image and labels acco ding o Eqs. (3.3)–(3.5)
3: pack esul s in 64 bi s om egis e s and s o e da a in global memo y .ou pu bu e
Figu e 4.7: Pseudocode o CA–Wa e shed synch onous CUDA ke nel execu ed in global memo y.
indica ing whe he he au oma on mus be u he p ocessed. The ke nel o he synch onous
upda ing o he au oma on is shown in Figu e 4.7.
In each call o he ke nel, da a a e ead om he inpu bu e in global memo y and a e
unpacked and au oma ically s o ed in egis e s (line 1). The pixels a e upda ed once (line 2)
as desc ibed by Eq. (3.3) and Eq. (3.4) i hei s a e is MP, and by Eq. (3.5) i hei s a e is
NM. These equa ions a e desc ibed in Sec ion 3.2.2. Finally, he esul ing da a a e packed and
s o ed in he ou pu bu e . The upda e ends when all egions ha e been looded.
Block–Asynch onous compu a ion on GPU
The CA–Wa e shed based on block-asynch onous compu a ion has he ad an age o eusing
in o ma ion wi hin a block, unlike he synch onous one, e icien ly exploi ing he sha ed
and cache memo ies o he GPU. The s o age equi emen s a e he same as o he block-
synch onous implemen a ion. The upda ing s age has been adap ed o pe o m in sha ed
memo y as many upda es inside a egion as possible (in a-block upda es), be o e pe o ming
a synch oniza ion among h ead blocks (in e -block upda es). Each egion is synch onously
upda ed (i.e. all cells wi hin a egion a e upda ed a each i e a ion), while he egions hem-
sel es a e asynch onously upda ed (an upda e o he en i e g id is pe o med a ce ain selec ed
s eps). Hence, his is a hyb id i e a i e p ocess ha includes block-asynch onous and block-
synch onous upda es. The pseudocode in Figu e 4.8 and Figu e 4.9 show he in e -block
upda es (lines 3–6) and he in a-block upda es (lines 2–5), espec i ely. The ke nels is placed
be ween he <and >symbols.
The in e -block upda ing loop is execu ed on he CPU and calls he asynch onous upda ing
ke nel ha is execu ed on he GPU. In his ke nel, o each block, once da a a e loaded in
sha ed memo y, he pixels a e modi ied acco ding o Eqs. (3.3) – (3.5) in an i e a i e in a-
block p ocess wi hin each egion o he image. Th eads wi hin a block a e synch onized
108 Chap e 4. Techniques and s a egies o e icien GPU compu ing
Inpu : one band image Ion he global memo y o he GPU
Ou pu : segmen a ion map
1: copy inpu da a I om global o ex u e memo y
2: <ini ialize cellula au oma on> . (Tex and GM)
3: while cellula au oma on is no s able do .in e –block upda ing
4: <asynch onous upda ing o he au oma on> . (SM)
5: synch oniza ion among blocks .global synch oniza ion
6: end while
Tex: ex u e memo y, GM: global memo y, SM: sha ed memo y
Figu e 4.8: Pseudocode o Asynch onous CA–Wa e shed implemen a ion on GPU.
Inpu : cellula au oma on packed in 64 bi s
Ou pu : cellula au oma on upda ed
1: load and unpack da a om global memo y o sha ed memo y .inpu bu e
2: while cellula au oma on is no s able wi hin a block do .in a–block upda ing
3: upda es image and labels acco ding o Eqs. (3.3)–(3.5) .(SM)
4: synch onize h eads wi hin he block .local synch oniza ion
5: end while
6: pack esul s in 64 bi s om sha ed memo y and s o e da a in global memo y .ou pu bu e
Figu e 4.9: Pseudocode o Asynch onous CA–Wa e shed CUDA ke nel execu ed in sha ed memo y.
locally a each s ep o he in a-block p ocess, so da a upda ed wi hin a block can be eused
om he sha ed memo y, which is much as e han he global memo y space (see Sec ion
4.1.4).
The in a-block upda ing ends when no new modi ica ions a e made wi h he a ailable da a
wi hin he egion. Then he da a in sha ed memo y a e packed and s o ed in global memo y.
The upda ing s age ends when all egions ha e been looded.
In o de o upda e he pixels a he edge o he block in his block-asynch onous imple-
men a ion, he sha ed memo y alloca ed o each egion mus be ex ended wi h a bo de o
size one. This ex a sha ed memo y space co esponds o he ap on illus a ed in Figu e 4.1(b)
ha is equi ed in iling/g id pa allel pa e ns when he local compu a ion also in ol es neigh-
bo ing da a. Thus, he ap on o one egion o e laps he adjacen egions. Th eads on he edge
o he block ha e o do ex a wo k loading he da a o he bo de .
4.2. Block–Asynch onous s a egy 109
The block-asynch onous algo i hm a oids poin s o global synch oniza ion ha a e cos ly
in execu ion ime, and e icien ly exploi s he sha ed memo y, which has lowe access imes
han he global memo y.
A i ac s- ee block–asynch onous compu a ion on GPU
The block–asynch onous CA–Wa e shed implemen a ion ob ains a co ec segmen a ion ac-
co ding o he wa e shed segmen a ion de ini ion. Thus, when non-minimum pla eaus exis
in he image, he algo i hm gi es a co ec segmen a ion; ne e heless, he wa e shed lines
may no ma ch he geodesic dis ance p ope ly. When he da a p opaga ion speed is simila
o all he cells, he algo i hm may gi e a good app oxima ion o he wa e shed lines. How-
e e , when compu ed by egions, i p esen s he p oblem o da a p opaga ion a he egion
bounda ies, which causes a i ac s as shown in he example in Figu e 4.10. Ini ially da a a e
p opaga ed wi hin he egion du ing he in a-block upda ing, and la e his is pe o med a he
egion bounda ies du ing he in e -block upda ing. The di e en speed o da a p opaga ion in
he in a-block and in e -block upda es esul in imp ope ly placed wa e shed lines. This si u-
a ion is isually obse ed as small i egula i ies in he wa e shed lines, as illus a ed in Figu e
4.10.
As a consequence o he asynch onous compu a ion by blocks some undesi able a i ac s
a ises and he quali y o he segmen a ion is sligh ly a ec ed. The asynch onous beha io o
he CA–Wa e shed implemen a ion is ixed by co ec ing he da a p opaga ion speed among
he blocks. The a i ac – ee block-asynch onous algo i hm is based on he applica ion o a
echnique known as wa e on [112] inc easing he quali y o he wa e shed lines ob ained.
The wa e on s a s om he lowe bo de o a pla eau (see Sec ion 2.3.2) and i e a i ely
Figu e 4.10: An image o size 128×128 pixels (le ), he co ec wa e shed line ob ained using 4-connec i i y
(middle), and he a i ac s p oduced by he asynch onous compu a ion using blocks o cells o size
32×32 ( igh ).
116 Chap e 4. Techniques and s a egies o e icien GPU compu ing
(a) (b)
Figu e 4.14: Example o a g eyscale a ibu e opening. (a) G eyscale image wi h i e connec ed componen s ( he
g ey le el is indica ed by he subsc ip , and he i- h componen wi hin a le el is indica ed by he
supe sc ip ) and he co esponding max- ee, (b) esul o he a ibu e opening on he g eyscale image
and he p uning o he max- ee.
can be cons uc ed by me ging he di e en sub- ees using he unique labels assigned by he
union- ind algo i hm.
Di ec implemen a ions wi hou building he max- ee a e also possible based on hie -
a chical FIFO and p io i y queues [170, 43, 97]. In [43] he il e ing and he looding o
labelling he componen s a e combined by passing he max- ee cons uc ion. I is conside ed
a di ec app oach only o a ea il e ing. The wo k p esen ed in [97] is based on [43] bu i can
4.2. Block–Asynch onous s a egy 117
Inpu : g eyscale image I
Ou pu : a ibu e opening
1: copy inpu da a I om CPU o he global memo y o he GPU
2: <labelling he connec ed componen s o Ia each g ey le el> . BA labelling (SM)
3: o each g ey le el h∈his og am(I)do
4: <me ge he egions o he connec ed componen s a le el h> . (GM)
5: <calcula e he a ibu e o each egion> . (GM)
6: <pe o m a ibu e il e ing> . (GM)
7: end o
GM s a es o compu a ion in global memo y and SM in sha ed memo y.
Figu e 4.15: Pseudocode o he g eyscale a ibu e opening on GPU.
be applied o a ibu es o he han a ea. One d awback o hese app oaches ha do no c ea e
he max- ee is ha he p uning ule mus be known a p io i. The g ey alue assigned o he
inal image a e emo ing a componen canno be e ie ed by a e sing he ee as i is no
cons uc ed.
In his hesis we p opose a GPU implemen a ion o g eyscale a ibu e openings and
closings wi hou using queues, h ough h eshold decomposi ion and me ging o connec ed
componen s. This p oposal is a membe o he g oup o di ec implemen a ions ha simula e
he max- ee [170, 43, 97].
The pseudocode in Figu e 4.15 shows he wo k low o he g eyscale a ibu e opening on
GPU p oposed in his hesis. The ke nels execu ed on GPU a e placed be ween <> symbols.
The a ea closing can be compu ed wi h he same algo i hm bu using he complemen o he
image.
The connec ed componen labelling (line 2) is pe o med by using he block–asynch onous
s a egy p oposed in his hesis. All he connec ed componen s o he image a e labelled a
once. Fi s , each pixel is gi en a unique label ha iden i ies i s posi ion wi hin he image in
a ow-majo o de . Then, an i e a i e p ocess p opaga es he minimum label be ween all he
connec ed neighbo s. This is simila o he block–asynch onous compu a ion desc ibed on
page 108. The upda ing s age is adap ed o pe o m in sha ed memo y as many in a-block
upda es as possible, be o e pe o ming he in e -block synch oniza ion.
Second, he image is p ocessed h ough h eshold decomposi ion (lines 3–7). A each
g ey le el h, om he highes o he lowe in ensi y, he connec ed componen s a g ey le el
h, which ha e been al eady labelled in he las i e a ion, a e me ged i hey ha e a common
118 Chap e 4. Techniques and s a egies o e icien GPU compu ing
bo de (line 4). This i e a i e p ocess simula es he max- ee om he lea es o he oo and
only keep in memo y he nodes a he cu en le el h. Once he componen s ha e been me ged,
he a ibu e o each one can be compu ed (line 5) in a new ke nel.
Finally, based on he alue o he a ibu e, a componen is il e ed a he cu en le el h
(line 6) i he c i e ion o ha componen is alse. We ha e used he il e ing max ule ha
p unes he b anches om he lea es up o he i s node ha needs o be p ese ed [144].
This p oposal could be used o compu e o he a ibu es han he a ea o a egion, simply by
modi ying he ke nel a line 5.
4.2.4 Resul s
In his sec ion we p esen he pe o mance esul s o he Block–Asynch onous s a egy ap-
plied o he asynch onous cellula au oma on o compu e he wa e shed ans o m, he opening
and closing by econs uc ion and he a ea a ibu e il e ing.
Expe imen al se up
The di e en implemen a ions based on he Block–Asynch onous (BA) s a egy ha e been
e alua ed on he In el quad-co e i7-860 mic op ocesso . The GPUs used in he expe imen s
a e he GTX 580 and he GTX TITAN based on he Fe mi and Keple a chi ec u es, espec-
i ely. The CUDA code has been compiled unde Linux using he n cc compile wi h he
CUDA oolki 4.2 (GTX 580) and 5.5 (GTX TITAN). The ha dwa e, he compu e capabili y
o he g aphic ca ds and he images used in hese es s a e desc ibed in Sec ion 2.9.1.
The e e ence codes o compa ison a e op imized OpenMP pa allel implemen a ions o
he CA–Wa e shed, he Fas Hyb id Recons uc ion (HRA) algo i hm [169] o he opening
and closing by econs uc ion, and an e icien implemen a ion based on he max- ee (min-
ee) [42] o a ibu e il e ing. These algo i hms will be desc ibed in he subsec ion whe e he
compa isons a e made. The pe o mance esul s analyzed a e exp essed in e ms o execu ion
imes and speedups. The execu ion imes we e ob ained as he a e age o 20 execu ions. In
all he es s, a connec i i y o ou pixels is used.
The da ase s used in he expe imen s a e wo images (Lena and CT Scan Head) and he
B ainWeb olume. The da ase s a e desc ibed in Sec ion 2.9.3. The wo images used a e
ep esen a i e cases o p ocessing small (Lena) and la ge (CT Scan Head and B ainWeb)
pla eaus, espec i ely. The p ocessing o la ge pla eaus ( egions o uni o m g ey alues)
makes i necessa y o p opaga e he labels h ough la ge egions o he image. This equi es
4.2. Block–Asynch onous s a egy 119
Size 512×512 1024×1024 2048×2048
T ans e ime 0.0022s 0.0082s 0.0321s
Size 45×54×45 90×108×90 181×217×181
T ans e ime 0.0013s 0.0073s 0.0581s
Table 4.1: CPU–GPU da a ans e imes o 2D and 3D images a di e en sizes.
mo e compu a ion ime han p ocessing small pla eaus. Thus he selec ed images ep esen
wo e y di e en cases ega ding o compu a ional cos o da a p opaga ion among blocks.
The CPU–GPU da a ans e s a e ca ied ou a he beginning and a e shown in seconds in
Table 4.1. This ime is he same independen ly o he applica ion whe e he BA app oach is
used.
CA–Wa e shed based on Block–Asynch onous compu a ion on GPU
In his sec ion we p esen he esul s o he ollowing GPU implemen a ions o he wa e shed
ans o m based on cellula au oma a: block-synch onous, block-asynch onous and a i ac s-
ee block-asynch onous implemen a ions1. Fi s , we ha e checked he co ec ness o he
asynch onous CA–Wa e shed implemen a ion by compa ing he numbe o segmen ed egions
ob ained by he GPU algo i hms o he numbe o egions ob ained by a sequen ial wa e shed
algo i hm o e he images.
Table 4.2 shows he numbe o egions c ea ed by he wa e shed ans o m, which is he
same o he CPU and GPU implemen a ions. The di e ence be ween he numbe o egions
a di e en esolu ions is due o he p ocess o scaling he image. The CT Scan Head and he
B ainWeb da ase s p esen la ge pla eaus and he e o e he numbe o egions is lowe (bu
la ge in size) han o he Lena image.
In he ollowing, he pe o mance is analyzed in e ms o occupancy, execu ion imes and
speedup.
– Analysis o he GPU Pa ame e s: The ini ializa ion and upda ing ke nels used on he
GPU implemen a ion, see he pseudocode p esen ed in Figu e 4.7 and Figu e 4.9, ha e been
1Pa o hese esul s ha e been published in P. Quesada-Ba iuso, D. B. He as, and F. A güello, “E icien 2D and
3D wa e shed on g aphics p ocessing uni : block-asynch onous app oaches based on cellula au oma a,” Compu e s
& Elec ical Enginee ing, ol. 39, no. 8, pp. 2638–2655, 2013.
120 Chap e 4. Techniques and s a egies o e icien GPU compu ing
Size 512×512 1024×1024 2048×2048
Lena 24958 25139 28521
CT Scan Head 6221 7300 13381
Size 45×54×45 90×108×90 181×217×181
B ainWeb 1115 5669 14348
Table 4.2: Numbe o egions gene a ed by he wa e shed ans o m.
analyzed acco ding o he esou ces a ailable on he GTX 580 (Fe mi a chi ec u e). This GPU
has 16 SMs wi h he ollowing limi s pe SM: 1536 h eads, 8 ac i e blocks, 32768 egis e s
o 32 bi s and 64 KB o on-chip memo y ha can be con igu ed as a sha ed memo y o 16
KB and 48 KB o he L1 cache o ice e sa (see Table 2.3 o a ull desc ip ion o he
GPU). Table 4.3 shows he maximum numbe o ac i e blocks based on he block size and
he on-chip memo y con igu a ion. Fo he ca_wa e shed_asynch onous ke nel, he eason
o selec ing he L1 con igu a ion wi h he emaining 16 KB being o he sha ed memo y is
ha he maximum numbe o ac i e blocks is gi en by he limi o 1536 h eads pe SM. As
desc ibed in Sec ion 4.2, 8 by es pe pixel a e equi ed o da a packing. Fo a block wi h
16×16 h eads, he sha ed memo y equi ed would be 2048 by es bu as he sha ed memo y
has been ex ended wi h an ap on o size one, each block needs 18×18×8 by es o his on-
chip memo y, i.e. 2.5 KB pe block. The e o e, conside ing a maximum o 6 blocks (1536
h eads) pe SM, a o al o 15 KB o sha ed memo y pe SM a e used.
Fo he case o he a i ac s- ee asynch onous p oposal (ca_wa e shed_asynch onous-
ee in Table 4.3), he numbe o simul aneously ac i e blocks pe SM is educed o ou . In
his case he limi ing ac o is he numbe o 32768 egis e s a ailable pe SM. The p oposal
equi es 26 egis e s pe h ead, which gi es a o al o 16×16×26 =6656 egis e s pe block,
Ke nel 16×16 32×16 32×32 8×8×4
ca_wa e shed_asynch onous L1 6 3 1 3
ca_wa e shed_asynch onous- ee L1 4 2 1 2
ca_wa e shed_asynch onous Sh 6 3 1 6
ca_wa e shed_asynch onous- ee Sh 6 3 1 6
Table 4.3: Numbe o ac i e blocks pe SM o he di e en ke nels based on he block size and he sha ed memo y
equi emen s. L1 indica es ha 48 KB a e used o he L1 memo y and 16 KB o he sha ed memo y.
Sh s a es o he opposi e con igu a ion. Analysis o CA–Wa e shed implemen a ions.
4.2. Block–Asynch onous s a egy 121
so he e a e enough egis e s in each SM o only 4 blocks. Rega ding he sha ed memo y use
in he a i ac s- ee ke nel, each pixel equi es 4 ex a by es o manage he geodesic dis ance
p ope ly, (see Algo i hm 2), so 18 ×18×(8+4) = 3888 by es pe block a e equi ed. By
using he Sh con igu a ion (48 KB o sha ed memo y), he limi in he numbe o ac i e
blocks is gi en by he block size.
– Pe o mance analysis: The OpenMP implemen a ion is based on he block-synch o-
nous app oach (see pseudocode on Figu e 4.5) and i uses 4 h eads scheduling he wo k
s a ically among he h eads by a loop cons uc dis ibu ing he i e a ions in o 4 chunks o
he same size (one pe h ead), in o de o e enly dis ibu e he wo kload among he h eads
and o achie e a high locali y in he da a accesses. The need o access da a ou side he egion
assigned o each h ead is no a p oblem in he OpenMP implemen a ion, as all he h eads
access he same memo y space. The algo i hm includes an implici synch oniza ion ba ie a
each s ep o he upda ing.
Table 4.4 gi es he pe o mance esul s ob ained in he GTX 580. The execu ion imes o
he GPU p oposals in his able include he CPU–GPU da a ans e ime. In all he es s, he
CA–Wa e shed based on block-asynch onous compu a ion ob ains high speedups o all he
image sizes. As shown in Table 4.4, he speedups also scale well wi h he size o he image;
i.e. om 9.0× o 13.6× o he block–synch onous implemen a ion o he Lena image up
o 11.7× o 22.2×wi h he block-asynch onous p oposal. When he image size inc eases, so
does he amoun o compu a ional wo k, he hund eds o a ailable h eads a e be e exploi ed.
The 3D GPU p oposals ob ain speedups o all he olume sizes, and he speedup alues in-
c ease wi h he olume size as he compu a ional load also inc eases. The pe o mance esul s
o he block-asynch onous p oposals a e always be e han o he synch onous implemen a-
ion; app oxima ely wice as good. The pe o mance esul s o bo h, he block-asynch onous
and he a i ac s- ee block-asynch onous app oaches a e e y simila .
We ocus now he es on he 2D images a a esolu ion o 2048×2048 pixels as he be-
ha io o p ocessing la ge pla eaus is be e app ecia ed in his case. When he image p esen s
la ge pla eaus he compu a ional cos o he wa e shed ans o m inc eases as he labels mus
be p opaga ed h ough la ge egions o he image. Compa ing he execu ion imes o he
block-synch onous and block-asynch onous app oaches (see Table 4.4), a speedup o 1.6x
is ob ained o he image o Lena while he speedup inc eases up o 4.3x o he CT Scan
image. The imp o emen o he block-asynch onous p oposal e sus he synch onous imple-
122 Chap e 4. Techniques and s a egies o e icien GPU compu ing
Lena (2D) 512×512 1024×1024 2048×2048
OpenMP (4 h eads) 0.0351s 0.1990s 1.2452s
GPU Synch onous 0.0039s (9.0×) 0.0188s (10.6×) 0.0916s (13.6×)
GPU Asynch onous 0.0030s (11.7×)0.0131s (15.2×)0.0562s (22.2×)
GPU A i ac s-F ee Async. 0.0034s (10.3×) 0.0158s (12.6×) 0.0736s (16.9×)
CT Scan (2D) 512×512 1024×1024 2048×2048
OpenMP (4 h eads) 0.4941s 2.8793s 15.0919s
GPU Synch onous 0.0305s (16.2×) 0.1436s (20.1×) 0.6992s (21.6×)
GPU Asynch onous 0.0093s (53.1×)0.0381s (75.6×)0.1628s (92.7×)
GPU A i ac s-F ee Async. 0.0126s (39.2×) 0.0522s (55.2×) 0.2353s (64.1×)
B ainWeb (3D) 45×54×45 90×108×90 181×217×181
OpenMP (4 h eads) 0.1337s 2.2611s 37.7378s
GPU Synch onous 0.0084s (15.9×) 0.0820s (27.6×) 1.1227s (33.6×)
GPU Asynch onous 0.0044s (30.4×)0.0451s (50.2×)0.5907s (63.9×)
GPU A i ac s-F ee Async. 0.0050s (26.5×) 0.0540s (41.8×) 0.7304s (51.7×)
Table 4.4: Pe o mance esul s including da a ans e imes (speedup in b acke s). Bes esul s in bold.
men a ion is be e o he second image; al hough, as shown in Table 4.4, p ocessing la ge
pla eaus akes mo e ime: 0.1628s o he CT Scan image while he Lena image only equi es
0.0562s. This is because o he block-asynch onous p oposal he in a-block upda ing allows
he labels o p opaga e as e among egions, especially in images wi h la ge pla eaus. I a
egion is en i ely wi hin a pla eau, he labels ha e o be p opaga ed om side o side o ha
egion. In his si ua ion, only one in e -block upda e and win a-block upda es a e needed,
whe e wis he wid h o he egion. The synch onous implemen a ion would need win e -
block upda es, wi h he consequen penal y o ans e ing da a om and o global memo y
a each s ep, wi h each one o hose s eps co esponding wi h a global synch oniza ion. The
block-asynch onous app oach educes he numbe o synch oniza ions among h ead blocks
and inc eases da a euse hanks o he in e - and in a-block upda ing scheme.
The dec ease in he numbe o synch oniza ions o he block-asynch onous p oposals is
illus a ed in Table 4.5, whe e he numbe o in e -block and in a-block upda es a e summa-
ized o he synch onous and he block-asynch onous implemen a ions and he es images.
Only he alues o he block-asynch onous implemen a ion a e shown, as he numbe s a e
he same o he a i ac s- ee p oposal. Fo he block-synch onous implemen a ions (on CPU
and on GPU) only in e -block upda es ake place in he sense ha a e each upda e o all he
4.2. Block–Asynch onous s a egy 123
Lena in e -block in a-block (min.) in a-block (max.) in a-block (a g.)
GPU Synch onous 114 — — —
GPU Asynch onous 16 22 195 108.5
CT Scan Head in e -block in a-block (min.) in a-block (max.) in a-block (a g.)
GPU Synch onous 1156 — — —
GPU Asynch onous 76 88 1248 668
Table 4.5: Numbe o upda es pe pixel o he block-synch onous and block-asynch onous implemen a ions o he
2048×2048 images.
pixels o he image one global synch oniza ion ope a ion is equi ed. Obse ing, o exam-
ple, he alues o he CT Scan image in he able, he numbe o in e -block upda es (i.e.
he numbe o global synch oniza ions equi ed) is 1156 o he synch onous implemen a ion.
Fo he block-asynch onous cases he numbe o in e -block upda es dec eases o 76 and he
o al numbe o asynch onous in a-block upda es pe block summing up all he i e a ions
anges om 88 o 1248, depending on he block, wi h 668 being he a e age alue o e all
he blocks. Hence, he numbe o upda es pe pixel is 1156, wi h he same numbe o co -
esponding global synch oniza ions o he synch onous implemen a ion, and an a e age o
668 local synch oniza ions wi h only 76 global synch oniza ions o he block-asynch onous
algo i hms. In he case o he Lena image, a simila dec ease is obse ed.
– Compa ison o o he wo ks: P oposals o di e en wa e shed algo i hms on he GPU
using shade s [88] and CUDA [171, 91, 81] ha e been p esen ed in he las ew yea s. In [171]
a new algo i hm is p esen ed based on he in oduc ion o a ch oma ic unc ion o es ablishing
he o de in which he oxels a e p ocessed. The expe imen s a e ca ied ou o e olume da a
se s, ob aining maximum speedups o 7×on a GTX295 when compa ed o he sequen ial
p oposal o he algo i hm, e en when la ge olume da a se s o up o 600 ×600 ×600 a e
conside ed. In ou case, he la ges olume conside ed was 181×217×181, 9 imes smalle ,
achie ing speedup alues o 63.9×on a GTX 580. Taking in o accoun ha he speedups o
ou block-asynch onous p oposals inc ease wi h he olume size, as shown in Table 4.4, and
ha ou expe imen s ha e p o ed ha he block-asynch onous p oposals scale by a ac o o
2× o 4×be ween he GTX 295 and he GTX 580 GPUs [139], we can conclude ha ou
p oposals ou pe o m he esul s in [171].
124 Chap e 4. Techniques and s a egies o e icien GPU compu ing
The algo i hm p esen ed in [91] is inspi ed by he d op o wa e pa adigm and pe o ms a
componen labelling and a pa h comp ession app oach [74]. I s esul s a e compa ed o a GPU
synch onous algo i hm o he wa e shed based on a CA [88], ou pe o ming i . Gi en ha
he expe imen s in [91] a e pe o med on an olde GPU han in ou case, we ha e execu ed
hem on ou GTX 580, ob aining simila speedup esul s o he ob ained wi h ou block-
asynch onous p oposal o he CA-wa e shed desc ibed in his wo k.
Opening and closing by econs uc ion on GPU
The opening and closing by econs uc ion GPU implemen a ion based on he block-asyn-
ch onous s a egy, see Sec ion 4.2.2, has been e alua ed on he GTX TITAN (Keple a chi-
ec u e)2. The block size is con igu ed wi h 32 ×8 h eads. Each block equi es only 340
by es o sha ed memo y, so he on-chip memo y is con igu ed wi h 48 KB o L1 cache.
The e e ence codes o compa ison a e he Fas Hyb id Recons uc ion (HRA) algo i hm in
CPU [169], and he GPU Sequen ial Recons uc ion (SR_GPU)3algo i hm p oposed in [87].
The pe o mance esul s analyzed a e exp essed in e ms o execu ion imes and speedups.
The speedups a e calcula ed wi h espec o he HRA (CPU) and he SR_GPU algo i hms.
The execu ion imes we e ob ained as he a e age o 20 execu ions. The da ase s used in he
expe imen s a e he Lena and he CT Scan Head images.
2Pa o hese esul s ha e been published in P. Quesada-Ba iuso, F. A güello, D. B. He as, and J. A. Benedik-
sson, “Wa ele -based classi ica ion o hype spec al images using ex ended mo phological p o iles on g aphics p o-
cessing uni s,” Selec ed Topics in Applied Ea h Obse a ions and Remo e Sensing, IEEE Jou nal o , ol. PP, no. 99,
pp. 1–9, 2015 (published online, p in edi ion pending).
3My hanks o P o . Ka as o sha ing his implemen a ion.
Lena 512×512 1024×1024 2048×2048
HRA (CPU) 0.1100s (1.0×) 0.1244s (1.0×) 0.1723s (1.0×)
SR_GPU (GPU) 0.0168s (6.5×) 0.0610s (2.0×) 0.2109s (0.8×)
BAR (GPU) 0.0027s (40.1×)0.0112s (11.1×)0.0485s (3.5×)
CT Scan Head 512×512 1024×1024 2048×2048
HRA (CPU) 0.1086s (1.0×) 0.1243s (1.0×) 0.1541s (1.0×)
SR_GPU (GPU) 0.0194s (5.6×) 0.0679s (1.8×) 0.2097s (0.7×)
BAR (GPU) 0.0026s (41.7×)0.0113s (11.0×)0.0388s (3.9×)
Table 4.6: Block–asynch onous mo phological econs uc ion esul s including da a ans e imes (speedup in
b acke s). Bes esul s in bold.
4.2. Block–Asynch onous s a egy 125
Fo his expe imen we ha e c ea ed a ma ke image J o each da ase Ias J(p) =
max{I(p)−h,0}, ha is known as he hmax ans o m. A alue h=10 was used o c e-
a e he ini ial ma ke .
The esul s o he h ee algo i hms a e shown in Table 4.6. Bo h, SR_GPU and BAR
algo i hms include he da a ans e om CPU o GPU memo y. I can be obse ed ha he
GPU p oposals ou pe o m he HRA algo i hm. Howe e , he SR_GPU algo i hm canno
bea he HRA algo i hm wi h he images o 2048×2048 pixels. I can be obse ed ha he
speedup dec eases by inc easing he size o he images. The eason is ha he HRA algo i hm
is op imized on CPU o p ocess only hose pixels ha need o be econs uc ed, while he SR_-
GPU and he BAR algo i hms a e based on a as e scanning o all he pixels o he image.
The p oposed algo i hm o e s a be e pe o mance in all cases. By pe o ming mul iple
scans in sha ed memo y a each i e a ion, his mo phological econs uc ion on GPU e i-
cien ly exploi s he sha ed memo y h ough he block-asynch onous upda ing p ocess. The
bes speedup is 41.7×ob ained on he CT Scan Head (512×512 pixels).
G eyscale a ibu e il e ing on GPU
This sec ion p esen s he esul s ob ained by he GPU g eyscale a ibu e opening (closing) al-
go i hm, desc ibed in Sec ion 4.2.3. We ha e e alua ed he pe o mance on he GTX TITAN
(Keple a chi ec u e). The a ailable esou ces o his GPU a e desc ibed in Sec ion 2.9.1.
The e e ence code o compa ison is an e icien implemen a ion based on he max- ee
(min- ee) p esen ed in [42] o classi ica ion o hype spec al images by using ex ended a -
ibu e p o iles (EAPs). The Uni e si y o Pa ia da ase , desc ibed in Sec ion 2.9.3, is used
in he es . The i s p incipal componen ex ac ed by PCA om his da ase is used o c e-
a e an EAPabased on a ea and an EAPdbased in he diagonal o he bounding box. The
h esholds (λ) o c ea ing each p o ile a e λ∈{36,49,169,361,625,1369} o he a ea and
λ∈{10,25,50,100,150,250} o he diagonal. These alues we e ex ac ed om [41].
Max- ee / min- ee Opening Closing TOTAL
(CPU) [42] GPU GPU GPU
EAPa0.9450 0.0825 0.1200 0.2025 (4.6×)
EAPd1.0331 0.0941 0.1335 0.2276 (4.5×)
Table 4.7: Pe o mance esul s o he g eyscale a ibu e il e ing (opening and closing) including da a ans e
imes o he i s PCA o he hype spec al image o he Uni e si y o Pa ia.
