TARGET DETECTION OF HYPERSPECTRAL
IMAGERY ON FPGAS
DETECCIÓN DE OBJETIVOS EN IMÁGENES
HIPERESPECTRALES SOBRE FPGAS
Juan Ma ín Bá ez Alonso
GRADO EN INGENIERÍA DE COMPUTADORES
FACULTAD DE INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
T abajo Fin de G ado
Sep iemb e 2020
Di ec o es:
Ca los González Cal o
José Manuel Mendías Cuad os
Resumen en cas ellano
En los úl imos años ha ocu ido un esu gimien o de la ca e a espacial mo i-
ado especialmen e po emp esas come ciales. Sus ae ona es son equipadas con una
mul i ud de senso es, siendo uno de ellos las cáma as hipe espec ales. Es e ipo de
cáma as oma imágenes en cien os de bandas espec ales di e en es, con el obje i o
de p opo ciona in o mación sob e el e eno.
A causa del g an amaño de las imágenes hipe espec ales, es as son en iadas a la
Tie a pa a su p ocesado, con el consecuen e cos e de ansmisión y almacenamien o.
P e e en emen e es as imágenes debe ían p ocesa se o comp imi se in si u pa a en ia
solo una acción de los da os ob enidos. Dados el en o no espacial y las ca ac e ís i-
cas es e ipo de algo i mos, las FPGAs o ASICs se pos ulan como un sis ema óp imo
pa a su implemen ación.
Es e abajo p esen a una implemen ación sob e FPGAs del algo i mo Reed-Xiaoli
de de ección de anomalías pa a imágenes hipe espec ales. Pa a su implemen ación
se ha ealizado un análisis de las ope aciones del algo i mo, cen ada en una e sión
en pun o o an e y o a en a i mé ica de en e os, y de las epe cusiones que ienen
cie as decisiones con la p ecisión que se alcanza. Demos ando de es a mane a
cómo algo i mos complejos con ope aciones en pun o o an e pueden se ejecu ados
en FPGAs al ans o ma los pa a u iliza a i mé ica de en e os.
Palab as cla e
Imágenes hipe espec ales, Algo i mo RX, A i mé ica de pun o o an e, A i -
mé ica de en e os, Ha dwa e econgu able, VHDL.
Abs ac
In ecen yea s he e has been a esu gence in he space ace, mo i a ed especially by
comme cial companies. Thei ai c a s a e equipped wi h a mul i ude o senso s, one
o hem being hype spec al came as. This ype o came a akes images in hund eds
o die en spec al bands, wi h he aim o p o iding in o ma ion o he g ound.
Because o he la ge size o hype spec al images, hey a e sen o g ound s a ions o
p ocessing, wi h he consequen cos o ansmission and s o age. P e e ably hese
images should be p ocessed o comp essed on si e and only a ac ion o he da a
ob ained should be sen . Gi en he spa ial en i onmen and he cha ac e is ics o
hese ypes o algo i hms, FPGAs o ASICs a e pos ula ed as an op imal sys em o
hei implemen a ion.
This wo k p esen s an FPGA implemen a ion o he Reed-Xiaoli algo i hm o anomaly
de ec ion o hype spec al images. Fo i s implemen a ion, an analysis o he ope a-
ions o he algo i hm has been made, cen e ed in a oa ing poin e sion and ano he
one in in ege a i hme ic, and o he epe cussions ha ce ain decisions ha e wi h
he p ecision ha is eached. Thus, demons a ing how complex algo i hms wi h
oa ing poin ope a ions can be execu ed in FPGAs by ans o ming hem o use
in ege a i hme ic.
Keywo ds
Hype spec al images, RX algo i hm, oa ing poin a i hme ic, in ege a i h-
me ic, econgu able ha dwa e, VHDL
Table o Con en s
Índice i
Lis o Figu es iii
Lis o Tables i
1 In oduc ion 1
1.1 Mo i a ion and objec i es . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Rela edwo k ............................... 2
1.2.1 Recongu able ha dwa e . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Hype spec al image y . . . . . . . . . . . . . . . . . . . . . . 6
1.2.3 Anomalyde ec ion ........................ 8
1.2.4 Compa ing oa ing and xed poin . . . . . . . . . . . . . . . 11
1.3 P ojec plan................................ 12
2 So wa e Model 13
2.0.1 Mean, de ia ion and co a iancce ma ix . . . . . . . . . . . . 14
2.0.2 In e se............................... 15
2.0.3 Ma ix mul iplica ion . . . . . . . . . . . . . . . . . . . . . . . 17
2.1 Adap ing he a i hme ic . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.1.1 DSPBlocks............................ 18
2.1.2 De e mining mul iplie size . . . . . . . . . . . . . . . . . . . . 19
2.1.3 Imp o ing accu acy . . . . . . . . . . . . . . . . . . . . . . . . 20
3 Implemen a ion 20
3.1 Gene al o e iew o he sys em . . . . . . . . . . . . . . . . . . . . . 21
3.2 Desc ip ionbymodule .......................... 21
3.2.1 Con ol .............................. 21
3.2.2 In e e .............................. 23
3.2.3 Meansub ac ........................... 26
3.2.4 Ma ix mul iplica ion . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.5 Coo dina e so e . . . . . . . . . . . . . . . . . . . . . . . . . 29
i
4 Resul s 30
4.1 Recongu able pla o m . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.2 Hype pec al image da ase s . . . . . . . . . . . . . . . . . . . . . . . 30
4.3 Adequacy o app oxima ion . . . . . . . . . . . . . . . . . . . . . . . 32
4.3.1 Floa ingpoin ........................... 32
4.3.2 Fixedpoin ............................ 32
4.3.3 Resul s o HYDICE . . . . . . . . . . . . . . . . . . . . . . . 33
4.3.4 Resul s o AVIRIS........................ 33
4.4 Compu a ional eciency . . . . . . . . . . . . . . . . . . . . . . . . . 36
5 Conclusions 38
ii

Lis o Figu es
1.1 Gene ic FPGA ha dwa e a chi ec u e . . . . . . . . . . . . . . . . . . 3
1.2 Eciency compa ison be ween CPU, GPU and FPGA o image p o-
cessing................................... 4
1.3 O e iew o an he e ogeneous FPGA . . . . . . . . . . . . . . . . . . 5
1.4 Compa ison be ween a s anda d and a hype spec al image . . . . . . 6
1.5 AVIRIS image o Cup i e, Ne ada . . . . . . . . . . . . . . . . . . . . 7
1.6 Sliding window used in some algo i hms . . . . . . . . . . . . . . . . 10
1.7 Pe o mance compa ison be ween xed and oa ing poin . . . . . . . 11
1.8 Gan diag amm o his wo k . . . . . . . . . . . . . . . . . . . . . . 12
2.1 P ecision o calcula ions wi h die en shi alues . . . . . . . . . . . 19
3.1 A schema ic o he op block . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Schema ic o he implemen ed in e e . . . . . . . . . . . . . . . . . 23
3.3 A i hme icpipeline............................ 24
3.4 Da a depency in he pipeline . . . . . . . . . . . . . . . . . . . . . . . 25
3.5 Schema ic o mean sub ac . . . . . . . . . . . . . . . . . . . . . . . . 26
3.6 Fi s p oposed me hod o he ma ix mul iplica ion . . . . . . . . . . 27
3.7 Second p oposed me hod o he ma ix mul iplica ion . . . . . . . . 27
3.8 Schema ic o he dual ma ix mul iplie . . . . . . . . . . . . . . . . . 28
3.9 Schema ic o he coo dina e so e . . . . . . . . . . . . . . . . . . . . 29
4.1 HYDICE senso in o ma ion and used da ase . . . . . . . . . . . . . 31
4.2 AVIRIS senso in o ma ion and used da ase . . . . . . . . . . . . . . 31
4.3 Spec al Angle Mappe algo i hm . . . . . . . . . . . . . . . . . . . . 33
4.4 Resul s o he HYDICE da ase . . . . . . . . . . . . . . . . . . . . . 34
4.5 Resul s o he AVIRIS da ase . . . . . . . . . . . . . . . . . . . . . 35
iii
Lis o Tables
2.1 DSP usage o mul iplie s wi h di e en wid hs . . . . . . . . . . . . . 18
3.1 La encies o some a i hme ic uni s . . . . . . . . . . . . . . . . . . . 24
4.1 Basic specica ions o he Vi ex 690T FPGA . . . . . . . . . . . . . 30
4.2 FPGA esou ce usage o e iew . . . . . . . . . . . . . . . . . . . . . 36
4.3 Implemen a ion la ency o e iew . . . . . . . . . . . . . . . . . . . . 36
4.4 Final esou ce and ime esul s o he implemen a ion . . . . . . . . 37
i
Chap e 1
In oduc ion
1.1 Mo i a ion and objec i es
Space explo a ion se es many pu poses, he mos ob ious being ga he ing in o ma-
ion abou ou plane and i s su oundings. Fo his pu pose, senso s capable o
ga he ing in o ma ion a e c ea ed, such as an ennas o elescopes ha a e used bo h
om he Ea h and sen aboa d spaceships. One o hose a e hype spec al came as,
which ake pic u es in hund eds o die en bands. Thei da a allows o nd objec s,
de ec ma e ials o iden i y p ocesses. As echnology ad ances, hese senso s e ol e
equi ing app op ia e p ocessing solu ions o in e p e he da a o comp ess i and
send i o g ound.
The objec i e o his wo k is he implemen a ion o one o hese algo i hms in a
way ha he p ocessing in he ai c a is p e e able o he ansmission o he aw
da a.
Fo his pu pose, die en algo i hms will be e alua ed and one will be chosen, mo e
specically, he Reed Xiaoli algo i hm. A  s implemen a ion o he oa ing poin
algo i hm will be done and i s ans o ma ion o in ege a i hme ic will be s udied.
This s ep is necessa y because he majo impedimen o hese algo i hms o be im-
plemen ed in ha dwa e is he high numbe and complexi y o i s ope a ions. Wi h
he a i hme ic well dened, i s implemen a ion will be adap ed and a compa ison o
accu acy and pe o mance be ween he  s oa ing poin e sion and he in ege
e sion will be made.
1
1.2 Rela ed wo k
In his sec ion we will e iew he s a e o he a on he use o FPGAs (eld p o-
g ammable ga e a ays) in space applica ions in gene al and implemen a ions ela ed
o he algo i hm de eloped in his wo k.
In [15] a s udy is ca ied ou on he cu en si ua ion o he use o FPGA on boa d
ai c a o hype spec al analysis and implemen a ions o wo algo i hms, ISRA and
N-FINDR, a e p esen ed. The esul s show nume ous ad an ages o FPGA o e
o he ypes o solu ions such as GPUs, such as i s smalle size and weigh and i s
esis ance o adia ion. In addi ion, hei econgu a ion capabili ies e en a e he
sys em is launched a e emphasized.
In [11] an implemen a ion o a a ge gene a ion algo i hm is p esen ed. I uses
an in e e based on he Gauss Jo dan elimina ion me hod, same as he one ha
will be used in his wo k, and he esul s a e p esen ed on he same pla o m.
In [9] a s udy o he same algo i hm ha will be implemen ed in his wo k is ca -
ied ou on an FPGA. The esul s a e posi i e wi h a educ ion in calcula ion ime
compa ed o so wa e-based solu ions. Howe e , his s udy was pe o med only on
a oa ing poin implemen a ion which limi ed i o he p ocessing o p e iously di-
mensionally educed hype spec al images.
In [21] he p ocessing o da a on boa d is p oposed wi h he aim o educing ne wo k
usage and accele a ing da a p ocessing. One o he s eps o his p ocessing is also
he RX algo i hm ha will be implemen ed he e.
In gene al, he p e ious wo ks p esen good esul s on hese sys ems and expec-
a ions o an inc ease o use, mo i a ed by mo e and mo e ad anced image cap u e
sys ems ha ake he ha dwa e o hei limi s.
2
O he me hods
Apa om he RX algo i hm, he e a e o he me hods o de ec ing anomalies,
al hough a no able numbe o hem a e based on RX.
Subspace me hods
Subspace me hods a e global and apply p incipal componen analysis (PCA) o sin-
gula alue decomposi ion (SVD) o he hype cube. The  s PCA/SVD bands a e
supposed o be he backg ound and a e emo ed die en ly by each me hod. No e-
mo ing enough bands means ha he anomalies can be los in he backg ound noise
and emo ing oo many would lead he anomalies o disappea . The de e mina ion
o he co ec numbe o bands o be emo ed is s ill unde s udy [6].
Subspace RX
In his me hod, he RX algo i hm is applied o a limi ed numbe
o PCA bands. The  s componen s a e disca ded.
RX a e o hogonal subspace p ojec ion [16]
In his me hod, he  s PCA/SVD
componen s dene he subspace o he backg ound and he da a is p ojec ed on o
an o hogonal space be o e applying XR.
RX a e pa ialling ou he clu e subspace [14]
In his me hod, clu e
eec on a pixel is disca ded componen wise aking each o i s spec al componen s
as a linea combina ion o i s high a iance p incipal componen s. The RX algo i hm
is applied o he esul s.
Complimen a y subspace de ec o [8]
This algo i hm is no based on RX. In
CSD, he p incipal componen s wi h highe a iance a e used o dene he subspace
o he backg ound and he o he PCs o dene he subspace o he a ge . The pixel
is hen p ojec ed on o he wo subspaces and he esul is he die ence be ween
hem.
Local me hods
In he local me hods he backg ound is de i ed om he neighbo ing pixels o su -
oundings o he pixel unde es (PUT). Two windows a e dened, a gua d and an
ex e io , and he neighbo s a e he pixels ha a e be ween hese wo. Some imes,
o example in local RX, a hi d one is used whe e he co a iance o he backg ound
is calcula ed in a window la ge han he a e age o he backg ound (see Figu e 1.6).
9

Quasi-local RX [12]
Quasi-local RX is a comp omise be ween global RX and local
RX, whe e he global co a iance ma ix is decomposed using eigen ec o /eigen alues.
The eigen ec o s a e main ained, bu he eigen alues a e eplaced by he maximum
local a iance, esul ing in lowe de ec o sco es in a eas wi h high a iance.
Co a iance window
Mean window
Gua d window
PUT
Figu e 1.6
:
Sliding iple window used in he local AD me hods.
Segmen a ion based me hods
In complex scenes i is dicul o assume ha he backg ound will be dened by
a no mal dis ibu ion, so me hods ha e been de eloped o sepa a e i in o die en
classes.
Class-Condi ional RX [13]
In his me hod he image is  s segmen ed and he
co a iance and mean ma ix calcula ed o each o hese classes. Each pixel will
co espond o he class in which i s RX alue is lowe .
The e a e mo e me hods wi hin hose based on segmen a ion, om hose using
s ochas ic unc ions such as Me hod Based on Mul i a ia e No mal Mix u e Models
o me hods based on Sel -o ganizing maps.
10
1.2.4 Compa ing oa ing and xed poin
In compu e sys ems, he e a e wo nume ical ep esen a ions o eal numbe s, xed
and oa ing poin . They ha e die en a i hme ic, which gi es hem die en ange
and esolu ion wi h he same numbe o bi s. The e o e, he e a e ce ain applica-
ions o pla o ms mo e akin o one o hem. Fo example, he abili y o oa ing
poin numbe s o con ain in he same numbe o bi s bo h e y la ge and e y small
numbe s and o adjus hei esolu ion acco dingly is e y a ac i e om he p o-
g amme 's poin o iew bu he simplici y o xed poin ope a ions allow hei use
in small mic ocon olle s o o sa e esou ces in FPGAs (see Figu e 1.7).
Figu e 1.7
:
A FIR l e , o iginaly implemen ed as a single-p ecision oa ing-poin
l e and con e ed o xed-poin . The xed-poin design shows bo h esou ce educ-
ion and la ency imp o emen s
Due o he high complexi y o hype spec al image analysis, cu en FPGAs ha e
li le capaci y o implemen some o hese algo i hms. The e o e, one o he objec-
i es o his wo k is o pe o m wo pa allel implemen a ions, one in oa ing poin
and ano he one in xed poin and compa e hei esul s.
11
1.3 P ojec plan
Fi s , an algo i hm and a ha dwa e pla o m a e chosen. Desi ably, his algo i hm
should be known and commonly ound in he li e a u e.
This algo i hm will be implemen ed in so wa e and his implemen a ion es ed wi h
eal images agains exis ing so wa e such as ENVI o Spec al Py hon.
The die en algo i hm s ages will hen be op imized o a ha dwa e a chi ec u e
and he ans o ma ion o he algo i hm om oa ing poin o in ege o xed poin
logic will be s udied.
This ans o ma ion equi es design decisions ha sac ice p ecision wi h he goal
o sa ing ha dwa e esou ces, so he unde lying ha dwa e will ha e o be conside ed.
Subsequen ly, a ha dwa e alida ion o he design will be ealized.
Finally, a s udy will be ca ied ou on he accu acy o he esul s ob ained.
Tasks
1 2 3 4 5 6 7 8 9 10
1
Resea ch algo i hms
2
So wa e impl.
3
Model ha dwa e
4
Ha dwa e impl.
5
Tes and alida ion
6
Repo esul s
Figu e 1.8
:
Gan diag am wi h an o e iew o mon hs and asks
12
Chap e 2
So wa e Model
The RX algo i hm has been chosen o his wo k because i is he benchma k o
his kind o algo i hms [6], [19], [16] and many exis ing algo i hms basing on RX in
some manne .
In o de o become amilia wi h he algo i hm and c ea e a pla o m whe e es s
can be easily pe o med, a so wa e implemen a ion has been made as a  s s ep.
The  s s ep is o di ide he algo i hm in o simple ope a ions:

Calcula e he mean, de ia ion and K co a iance ma ix o he image

Calcula e
K−1
ha is, he in e se o he co a iance ma ix

Calcula e
δRX
o each pixel in he image

So he esul s
13
2.0.1 Mean, de ia ion and co a iancce ma ix
One o he bo lenecks in his ype o FPGA-based sys ems is he inpu and ou pu
o da a [20]. Since he calcula ions o mean, a iance and co a iance ma ix need he
o iginal ma ix -a cube- o his, i has been decided o calcula e hese in a CPU and
ansmi he esul s o he FPGA. In addi ion, he ope a ions a e ela i ely simple
o a CPU. Nex , he pseudocode o he h ee is p esen ed.
Algo i hm 1
Pseudocode o he mean, de ia ion and co a iance ma ix
1:
. bands
: numbe o bands in he image
2:
. pixels
: numbe o pixels in he image
3:
. A
: he image in he o m o a 2D ma ix wi h
pixels ×bands
4:
.T
is used o deno e he anspose o a ma ix
5:
unc ion
mean
(
A
)
6:
o
i←0
o
bands −1
do
7:
sum ←0
8:
o
j←0
o
pixels −1
do
9:
sum ←sum +A[i][j]
10:
mean[i]←sum/pixels
e u n
mean
11:
unc ion
de ia ion
(
A, mean
)
e u n
AT−mean .
This ope a ion is a ma ix sub ac ion
12:
unc ion
co a iance
(
de ia ion
)
e u n
de ia ionT∗de ia ion/(pixels −1)
The co a iance, a
band2
ma ix is hen ansmi ed o he FPGA o calcula e i s
in e se.
14

2.0.2 In e se
Choosing he algo i hm
Be o e s a ing he implemen a ion, se e al algo i hms o pe o m he in e se ha e
been s udied.
QR Fac o iza ion [4]:
QR ac o iza ion b eaks down he
A
ma ix in o he p od-
uc o wo ma ices
A=QR
, wi h
Q
being an o hogonal ma ix and
R
a supe io
iangula ma ix. Wi h his iangula ma ix i becomes easy o calcula e he in-
e se. Howe e , al hough QR ac o iza ion can be ecien ly pe o med on a powe ul
ma ix mul iplica ion module o se e al modules ha can be execu ed simul ane-
ously, such as in a GPU, i does no ake ad an age o he capabili ies p o ided by
ou sys em such as a bi a y wid h a i hme ic uni s.
Gauss Jo dan elimina ion me hod [11]:
The Gauss Jo dan me hod dic a es
ha i we ha e a
A
ma ix ha can be ans o med in o he iden i y ma ix h ough
elemen a y ope a ions, hese same ope a ions ans o m he iden i y ma ix in o
A−1
.
Since i is possible o execu e hese elemen a y ope a ions in an en i e ow a once
and he ope a ions be ween ows a e independen , his me hod is easily pa alleliz-
able. The e o e, his was he chosen me hod.
Gene ally speaking, he execu ion o he algo i hm akes place in such a way ha :
1. An iden i y ma ix is gene a ed
2. The same ope a ions a e pe o med on bo h ma ices un il he
A
ma ix is
ans o med in o he iden i y ma ix
3. The esul is in he ma ix gene a ed in he  s s ep
As seen in he ollowing pseudocode, hese elemen a y ope a ions a e pe o med in
3 s eps:
15
Algo i hm 2
Pseudocode o he Gauss Jo dan me hod
1:
A
: a squa e ma ix wi h he size
n∗n
2:
A−1
: an iden i y ma ix wi h he size
n∗n
3:
unc ion
in e se
(
A
)
4:
o
i←0
o
n−1
do
.
Fo wa d elimina ion o build he uppe iangula
ma ix
5:
.
ow
i
ac s as he pi o
6:
i
A[i][i]=0
hen
.
I he la e di iso is 0
7:
o
j←i+ 1
o
n−1
do
8:
i
A[i][j]6= 0
hen
9:
A[i]←A[j], A[j]←A[i]
10:
o
j←0
o
n−1
do
11:
A−1[j]←A−1[j]−A−1[i]∗(A[j][i]/A[i][i])
12:
A[j]←A[j]−A[i]∗(A[j][i]/A[i][i]) .
These wo lines un in pa allel
13:
.
A e a comple e i e a ion o he ou e loop, he pi o con ains he
desi ed o m
14:
15:
16:
o
i←n−1
o
0
do
.
Backwa d elimina ion o build a diagonal ma ix
17:
o
j←i−1
o
0
do
18:
A−1[j]←A−1[j]−A−1[i]∗(A[j][i]/A[i][i])
19:
A[j]←A[j]−A[i]∗(A[j][i]/A[i][i]) .
These wo lines un in pa allel
20:
21:
22:
o
i←0
o
n−1
do
.
Las di ision o build iden i y ma ix
23:
A−1[i]←A−1[i]∗(1/A[i][i])
24:
A[i]←A[i]∗(1/A[i][i])
25:
.
The e is no need o upda e he alues in he s a ing ma ix
e u n
A−1
16
2.0.3 Ma ix mul iplica ion
Wi h he in e se o he con a iance ma ix calcula ed in he FPGA, he eal RX
algo i hm can con inue o be pe o med, whe e a hype spec al pixel is mul iplied
wi h his in e se. This calcula ion will equi e he CPU o ansmi he o iginal
image, he o iginal image nex o he a e age, o he de ia ion al eady calcula ed o
he FPGA.
The RX algo i hm dic a es ha :
x(x)=(x−µ)TK−1
N×N(x−µ)
K−1
N×N
being he in e se ma ix wi h a dimension o
N×N
,
(x−µ)
being he de ia ion o a pixel a dimension o
N×1
and
(x−µ)T
i 's anspose, wi h a dimension o
1×N
.
In his s ep, he in e se ma ix ge s eec i ely mul iplied by a unique pixel ac oss all
bands. Th ough ow educ ion, a single alue o his pixel is eco e ed which can
hen be mapped o a 2d image.
Since he ope ands a e he e ogeneous, use can be made o he associa i e law on
ma ix p oduc s ha dic a es ha :
A∗(B∗C) = (A∗B)∗C
o op imize he ope a ion.
In he implemen a ion sec ion, a s udy on wha al e na i e o use will be ca ied
ou , as his depends hea ily on he ha dwa e a chi ec u e.
2.1 Adap ing he a i hme ic
As shown be o e in Figu e 1.7, oa ing poin a i hme ic ope a ions a e e y inecien
compa ed o xed poin ope a ions. In he nex chap e a ans o ma ion s a egy
will be dened and he s eps ollowed o make his ansi ion will be shown.
Taking ad an age ha he RX algo i hm only needs ela i e and no exac alues, ie,
he highes alue ound in he esul s will be he mos anomalous (see 1.2.3) ega d-
less o whe he i exceeds a ce ain h eshold o no , he xed-poin ep esen a ion
may be simplied by igno ing he ac ional pa and keeping only he in ege .
17
2.1.1 DSP Blocks
The DSP blocks a e p e ab ica ed ci cui s ound nex o he FPGA logic and im-
plemen a i hme ic ope a ions. These blocks allow o pe o m ope a ions mo e e-
cien ly and ope a e a highe equencies han equi alen logic in he ab ic, besides
no occupying space in i . Howe e , as hey a e p e ab ica ed blocks, hey do no
oe he same exibili y as he es o he FPGA logic. This implies ha he size o
he ope ands and he cos o ope a ion esou ces will no always be p opo ionally
ela ed. The e o e, die en wid hs ha e been es ed and hei esou ce usage has
been no ed.
The esul s o hese es s o mul iplica ion a e in he ollowing able:
Wid h ope and A Wid h ope and B DSP48 Slices used
25 18 1
35 25 2
52 24 3
42 35 4
64 25 4
52 42 6
Table 2.1
:
Depending on he wid h o he ope ands, he ope a ion will use a die en
amoun o esou ces (da a ob ained o signed mul iplica ion in Vi ado 2019.2 on
Xilinx Se ies 7 chips)
Fo sub ac ion ope a ions up o 48bi s, only one DSP is used, so hey a e no ex-
pec ed o equi e mo e han one block.
The di isions canno be implemen ed by his ype o blocks, so hey will use s anda d
logic and can be used wi h an a bi a y wid h.
Wi h his, da a o all he ope a ions ha a e going o be ca ied ou in he FPGA
is eco ded.
18
One o he ope ands is he ow , which is used a wo die en imes wi hin he
algo i hm (see Figu e 3.4). Since a second ead on he BRAM canno be done since
i is busy pe o ming he ead o he nex ope a ions, his da a is s o ed a he ime
o eading in a FIFO and will be e ched when needed.
A−1[j]←A−1[j]−A[i]∗A[j][i]/A[i][i]
Figu e 3.4
:
As can be seen in he algo i hm, ow j is used a wo die en imes.
Addi ionaly, i can be obse ed ha in he  s s ep in which he uppe iangu-
la ma ix is cons uc ed, he algo i hm equi es a check on he pi o ow and a
possible exchange o ows. This is necessa y because his alue is la e he di idend,
so a 0 would cause a ailu e in he calcula ion.
BRAM memo y eadings ha e a la ency cycle, so eading an inapp op ia e alue wo
cycles in a ow -in he case o eading an inapp op ia e and hen an app op ia e
alue, he e would be he possibili y o pe o ming an inplace ow swap wi h he
pi o and he ow jus a e i - would no only add la ency o he calcula ion bu
also inc ease he complexi y o he module. The e o e, he di idend checks a e done
on he w i es, eco ded in a enaming able ha will be checked a he ime o ead-
ing. This ensu es ha he eads will always be alid o he calcula ion. In he case
o he e y  s di ision, his di idend comes di ec ly om he CPU and he uppe
module
con ol
is esponsible o eo de ing his ow i necessa y.
This enaming able is loca ed in egis e s, so i is possible o access i wi hou any
la ency and as i only con ains indexes, i does no o e load he FPGA esou ces.
In addi ion, his able is local, so he esul s ha e o be eo de ed in he RAM i sel
be o e lea ing he in e se module. Since hese swaps only occu in he calcula ion o
he uppe iangle, he lowe iangle can be used o eo de hem. The eo de ing
sys em is e y simple, he da a en e s he pipeline acco ding o he o de ha exis s
in he enaming able and is w i en in i s na u al o de . This implies ha he e-
sul s o his eo de ing will be co ec as long as bo h ows ha ha e been o a ed
a e a he same ime in he p ocessing pipeline, which in he case o xed poin is
app oxima ely 90 in size. Expe imen al esul s show ha i is a ely necessa y o
o a e ows -al hough enough o ecommend he inclusion o a me hod o deal wi h
i -, and ha hese o a ions a ely exceed one o wo posi ions in he pipeline.
In he ans o ma ion o in ege a i hme ic i was disco e ed ha he calcula ion
o he in e se is he one in oducing mo e e o in he nal esul s o he algo i hm,
25

he e o e an exhaus i e s udy on how o minimize i has been made. Fo his i has
been necessa y o educe he alues in which he limi ed p ecision p oduced o e ows
and inc ease small alues o gi e hem mo e weigh in he ope a ions. By pe o m-
ing he ope a ions o iden i y gene a ion, uppe iangle, lowe iangle and diagonal
independen ly, i has been possible o place die en shi alues and u he ene
he esolu ion o he algo i hm. These ope a ions a e pe o med by he
shi
p ocess.
I should also be said ha he e is an e o in he gene a ion o Xilinx di ide s. When
you en e numbe s nea he p ecision limi you lose con ol o he sign. The e o e,
di _x
, a p ocess ha con e s all he en e ed ope ands in o posi i es and sa es
hei posi ion in a pipeline has been placed be o e he di ision. When he esul s a e
p oduced, he ag is checked in he pipeline, he nega i e is calcula ed and eplaced
i necessa y.
3.2.3 Mean sub ac
Figu e 3.5
:
Schema ic o mean sub ac .
The
mean sub ac
module ecei es he calcula ed a e age and he o iginal pixels
o he image and sub ac s hem. This calcula ion is he de ia ion and al hough
i had al eady been calcula ed by he CPU, i is possible ha he la e disca ds
he da a o ee up space. The calcula ion o he a e age is equi ed because i is
assumed ha i s size being much smalle , he CPU can keep i in memo y. In case
he de ia ion can be ecei ed di ec ly om he CPU, his module can be simply
dele ed. The module ecei es he elemen s om he uppe module ha eads hem
om he same FIFO. The  s elemen s a e he a e age and a e s o ed in a BRAM
ha is ea ed as a ci cula bue , and he ollowing elemen s a e di ec ly sub ac ed
and e u ned o he uppe module again.
26
3.2.4 Ma ix mul iplica ion
As no ed abo e (see 2.0.3), his calcula ion can be implemen ed in wo die en ways.
Following will be a compa ison o he  s equi ed mul iplica ion in bo h me hods:
(x−µ)TK−1
N×N
: A ow om he in e se and he whole column o he
de ia ion ge ead, each elemen mul iplied wi h i s co esponden and
all p oduc s added oge he . I s alls we e o be a oided, his sum would
need o be compu ed e e y cycle, which can easily be achie ed wi h an
adde ee.


a b c
d e
g h i

∗

1
2
3

=

1∗a+ 2 ∗b+ 3 ∗c
1∗d+ 2 ∗e+ 3 ∗
1∗g+ 2 ∗h+ 3 ∗i


Figu e 3.6
:
Fi s p oposed me hod o he compu a ion o a single pixel: ed, blue
and g een ep esen da a p ocessed in he  s , second and hi d cycles espec i ely.
No e ha he en i e de ia ion da a o ha pixel ge s used e e y cycle
K−1
N×N(x−µ)
: The in e se ge s also ead ow by ow, bu he de ia ion
ma ix only by elemen s. Each elemen o he  s ow o he ma ix ge s
mul iplied wi h he  s elemen o he de ia ion, he esul accumula ed,
and con inued wi h he nex pai ow/elemen . This goes o
N
cycles,
ha is, a whole in e se ma ix and a whole pixel in he de ia ion ma ix.
The esul is
N
accumula ed alues which ge ushed e e y
N
cycles,
which ends up being he same h oughpu as he o me me hod.

123
∗

a b c
d e
g h i

=
1*a
+
2*d
+
3*g 1*b
+
2*e
+
3*h 1*c
+
2*
+
3*i

Figu e 3.7
:
Second p oposed me hod: ed, blue and g een ep esen da a p ocessed in
he  s , second and hi d cycles espec i ely. He e only an elemen o he de ia ion
da a ge s accessed each cycle.
While bo h me hods ha e equi alen cos in ime - he o me has he added
la ency o he adde ee, he la e he la ency o he accumula o s- and also simila
27
cos in DSP usage, da a inpu by ow is less axing on he CPU and i s FIFO s uc u e
can be eused o he second mul iplica ion. Hence o h, he second app oach was
chosen.
Figu e 3.8
:
Schema ic o he dual ma ix mul iplie
The second mul iplica ion is simila in bo h s eps, a
1×N
by
N×1
mul ipli-
ca ion. One ope and comes e e y cycle and each
N
cycles all p oduc s ge added
oge he . This sum is ealized h ough an accumula o .
The module con ains h ee subp ocesses:

 s _mac
eads he in e se and pe o ms i s mul iplica ion wi h he ecei ed
de ia ion. This de ia ion is also s o ed in a FIFO. The p oduc s a e hen
accumula ed ill a whole pixel has been compu ed.

second_mac
s o es he esul s o
 s _mac
in egis e s and pe o ms he mul-
iplica ion wi h da a om he FIFO, wi h he esul being accumula ed. E e y
cycle, he egis e s a e shi ed so a new mul iplica ion is done.

w i e_p oc
con ols he w i ing o he esul s om
second_mac
o he so e
and compu es he coo ds.
28
3.2.5 Coo dina e so e
Figu e 3.9
:
Schema ic o he coo dina e so e
This module ecei es a alue and a pai o coo dina es e e y
bands
cycles. These
alues a e w i en in a BRAM memo y ha ac s as an o de ed lis . Each en e ed
alue is compa ed wi h he head o he lis , he highes alue is sa ed and he o he
is sa ed in a empo a y a iable, compa ed wi h he second alue in he lis , and so
on. Since a alue is ecei ed each
bands
, he maximum numbe o possible alues o
be s o ed in his lis is also
bands
. The es o he alues a e disca ded. When he
las alue has been in oduced, he module communica es he highes pixels, ha is,
he mos anomalous ones, o he supe io module so ha hey a e communica ed o
he CPU.
29
Chap e 4
Resul s
4.1 Recongu able pla o m
The a chi ec u e desc ibed in he p e ious sec ion has been implemen ed using he
VHDL language. To es i s co ec ope a ion, he Vi ado en i onmen and he
Vi ex 690T FPGA 4.1 ha e been used. Al hough i is no a adia ion-p o ec ed
FPGA, he a chi ec u e o his algo i hm is scalable so ha i s adap a ion o o he
senso sizes o FPGAs should no be a p oblem.
4.2 Hype pec al image da ase s
Two hype spec al images ha e been used o he wo k, one aken by he HYDICE
senso and he o he by he AVIRIS senso . Bo h images a e commonly used as
e e ence in hype spec al applica ions.
In he eld o he scene cap u ed by HYDICE, 15 panels o die en sizes we e
placed on a eld in a 3 x 5 me e congu a ion. The ollowing images show a alse
colo image wi h he bands
50
,
37
, and
17
as ed, g een and blue espec i ely [10]
and he loca ion o he panels as de ec ed by so wa e.
Pa numbe Slices Logic cells Flip-Flops BRAM DSP Slices
XCE7VX690T 108,300 693,120 866,400 1,470Kb 3,600
Table 4.1
:
Basic specica ions o he Vi ex 690T FPGA
30

Ho izon al es 64
Ve ical es 64
Bands 210 (169*)
Spec al es 400 - 2500nm
Spa ial es 1,56me e /pixel
Size 1,6 MB
Figu e 4.1
:
HYDICE senso in o ma ion [3], image in alse colo and anomaly
map. *In his wo k, images and esul s a e epo ed o 169 bands
The image aken by he AVIRIS senso was aken on Sep embe 16, 2001,  e days
a e he e o is a acks ha b ough down he WTC owe s and i s su ounding
buildings. The spa ial esolu ion o his image is e y high because a e y low al-
i ude igh was pe o med. Along wi h he alse colo image, an image wi h he
anomalies de ec ed by so wa e is p o ided. To ease he ecogni ion o hese anoma-
lies, a ci cle has been pain ed a ound each g oup o anomalues o he  s 30.
Ho izon al es 614
Ve ical es 512
Bands 224
Spec al es 360 - 2500nm
Spa ial es 1,7me e /pixel
Size 140 MB
Figu e 4.2
:
AVIRIS senso in o ma ion [2], image in alse colo and anomaly map
31
4.3 Adequacy o app oxima ion
4.3.1 Floa ing poin
The esul s p o ided by he oa ing poin e sion o his sys em a e he same as
hose p o ided by he equi alen so wa e e sion, so i can be conside ed alid.
4.3.2 Fixed poin
The xed poin e sion o he sys em is an app oach o he oa ing poin sys em
wi h he in en ion o main aining he highes possible accu acy wi h limi ed use o
esou ces. The e o e, he esul s a e die en and an assessmen o hei accu acy
mus be made. Fo his pu pose, h ee me ics ha e been used.
In he  s and simples , i has been e ied ha he numbe o de ec ed anomalies
can be ound in he  s x posi ions in bo h esul s, ega dless o he o de .
Ex ending he p e ious s a egy, i has been checked o he non-coinciding elemen s,
i any neighbo has been de ec ed in he en i onmen . A neighbo is dened as an
adjacen pixel, bo h in a s aigh line and in diagonal.
Finally, he  s s a egy has been ex ended again, his ime i has been checked
i o he non-coincidences an anomaly wi h a spec al simila i y o less han 5 de-
g ees has been ound.
Spec al simila i y
The Spec al Angle Mappe (SAM) is a physics-based spec-
al classica ion ha uses an n-D angle o ma ch pixels wi h e e ence spec a. The
algo i hm (see sec ion 4.3.2) de e mines he spec al simila i y be ween wo spec a
by calcula ing he angle be ween he spec a and ea ing hem as ec o s in a space
wi h a dimensionali y equal o he numbe o bands. This echnique, when used in
calib a ed eec ance da a, is ela i ely insensi i e o he eec s o illumina ion and
albedo.
32
α= cos−1




nb
P
i=1
i i
nb
P
i=1
2
i1/2nb
P
i=1
2
i1/2





α
= spec al angle be ween ec o s
nb = numbe o spec al bands
= a ge pixel
= e e ence pixel
Figu e 4.3
:
Spec al Angle Mappe algo i hm
4.3.3 Resul s o HYDICE
E e y pixel is ound in he same o de in e e ence and simula ed calcula ions. Also,
since hose pixels a e ound equally, i is ob ious ha hey a e also ound as neigh-
bo ing pixels and a e spec ally simila . Since i is an image aken o es he senso ,
he a ge s a e big and clea , and he image is qui e easy o analyze.
4.3.4 Resul s o AVIRIS
The WTC image is mo e complex and he de ec ion o exac pixels and neighbo s
quickly alls. Howe e , he spec al signa u es ma ch o he mos pa , especially
conside ing he numbe o eal ho spo s ound in he image. The e o e, he esul s
can also be aken as success ul.
33
Figu e 4.4
:
A diag am showing simila i ies be ween e e enced and achie ed esul s
and e e ence and achie ed esul s mapped as in he o iginal image o he HYDICE
da ase
34
[19] Dal on Rosa io. A semipa ame ic model o hype spec al anomaly de ec ion,
Janua y 2012.
[20] Qingshan Tang, Habib Meh ez, and Ma hieu Tuna. Mul i-FPGA p o o yp-
ing boa d issue: he FPGA I/O bo leneck. In
2014 In e na ional Con e -
ence on Embedded Compu e Sys ems: A chi ec u es, Modeling, and Simula ion
(SAMOS XIV)
, pages 207214, July 2014.
[21] James Theile , Be na d Foy, Clai a Sa, and S e en P. Lo e. Onboa d CubeSa
da a p ocessing o hype spec al de ec ion o chemical plumes. In Da id W.
Messinge and Miguel Velez-Reyes, edi o s,
Algo i hms and Technologies o
Mul ispec al, Hype spec al, and Ul aspec al Image y XXIV
, page 5, O lando,
Uni ed S a es, May 2018. SPIE.
[22] Xin Zhou, No ihi o Tomagou, Yasuaki I o, and Koji Nakano. Ecien Hough
T ans o m on he FPGA using DSP Slices and Block RAMs. In
2013 IEEE In-
e na ional Symposium on Pa allel Dis ibu ed P ocessing, Wo kshops and Phd
Fo um
, pages 771778, May 2013.
41