Ap oximación a la Implemen ación de Aplicaciones
Ae o-espaciales en Ha dwa e
Víc o Diges Teijei a
GRADO EN INGENIERÍA DE COMPUTADORES. FACULTAD DE
INFORMÁTICA
UNIVERSIDAD COMPLUTENSE DE MADRID
CURSO 2014-2015
T abajo Fin de G ado en Ingenie ía de Compu ado es
29/06/2015
Di ec o es:
Ma cos Sánchez-Elez Ma in
Inmaculada Pa dines Lence
Au o ización de di usión
Víc o Diges Teijei a
29/06/2015
El/la abajo i man e, ma iculado/a en el G ado en Ingen ía de Compu a-
do es de la Facul ad de In o má ica, au o iza a la Uni e sidad Complu ense
de Mad id (UCM) a di undi y u iliza con ines académicos, no come ciales
y mencionando exp esamen e a su au o el p esen e T abajo Fin de G ado:
Ap oximación a la Implemen ación de Aplicaciones Ae o-espaciales en Ha d-
wa e, ealizado du an e el cu so académico 2014-2015 bajo la di ección de Ma -
cos Sánchez-Elez Ma ín e Inmaculada Pa dines Lence en el Depa amen o de
A qui ec u a de Compu ado es y Au omá ica, y a la Biblio eca de la UCM a
deposi a lo en el A chi o Ins i ucional E-P in s Complu ense con el obje o de
inc emen a la di usión, uso e impac o del abajo en In e ne y ga an iza su
p ese ación y acceso a la go plazo.
Resumen
En la ac ualidad, los sis emas de ha dwa e econ igu able es án muy ex endidos
en el en o no ae oespacial. Es o es debido a su g an po encia compu acional
compa ada con la de soluciones so wa e. En es e p oyec o se analizan las
múl iples aplicaciones de las FPGAs en es a indus ia, y cómo la in es iga-
ción espacial y de de ensa han lide ado el desa ollo de sis emas ae onáu icos
elec ónicos. Es os es án p esen es hoy en día en la mayo ía de ae ona es
come ciales. Además, se in oduci án b e emen e los e ec os de la adiación
del espacio en los elemen os elec ónicos, explicando cómo a ec an a las me-
mo ias y los ci cui os y cómo pueden se de ec ados y co egidos po la FPGA.
Se ha escogido el p ocesado de ideo en iempo eal como aplicación ob-
je i o de es e abajo, mos ando las ca ac e ís icas de las FPGAs que pueden
se explo adas pa a ob ene esul ados con muy poca la encia. Se ha u iliz-
ado la he amien a Ma lab pa a simula los algo i mos, indicando al mismo
iempo cómo pod ían se segmen ados en una FPGA. Pa a mejo a los es-
ul ados se ha desa ollado un p ocedimien o pa a la de ección de obje os pa a
una is a de cáma a mó il, basado en la eliminación de uido de la imagen y
en humb alado.
Palab as cla e
FPGA, Ae oespacial, Visión po Compu ado a, P ocesamien o de Video,
Reconocimien o de Obje os.

Abs ac
Nowadays, econ igu able ha dwa e sys ems a e widely used in he ai space
en i onmen . This is hanks o hei g ea compu ing powe in compa ison o
so wa e solu ions. In his p ojec we analyze he mul iple applica ions o FP-
GAs in his indus y, and also how he space and de ense esea ch ha e lead
he de elopmen o elec onic ae onau ic sys ems. They a e now p esen in
mos o he comme cial ai c a s. In addi ion, we b ie ly in oduce he e ec s
o space adia ion in elec onic, explaining how hey a ec memo ies and ci -
cui s and how hey can be de ec ed and co ec ed by an FPGA.
Real ime ideo p ocessing was chosen as a a ge applica ion o his wo k,
showing how FPGA’s cha ac e is ics can be exploi ed o ob ain esul s wi h
e y low la ency. Ma lab ool was used o simula e he algo i hms, p o iding
insigh on how hey could be pipelined in an FPGA. In o de o imp o e he
esul s an objec de ec ion p ocedu e o a mo ing came a iew was de eloped,
based on noise emo al and h esholding.
Keywo ds
FPGA, Ae ospace, Compu e Vision, Video P ocessing, Objec Recogni-
ion.
Con en s
Index i
1 FPGA Applica ions in a ionics 1
1.1 Fligh Con ol............................ 2
1.2 Na iga ion and Moni o ing . . . . . . . . . . . . . . . . . . . . . 3
1.3 Augmen edVision ......................... 4
1.3.1 Real Time analysis . . . . . . . . . . . . . . . . . . . . . 4
1.3.2 In elligen T anspo . . . . . . . . . . . . . . . . . . . . 5
1.3.3 Imme si e Displays . . . . . . . . . . . . . . . . . . . . . 5
1.3.4 Image S abiliza ion . . . . . . . . . . . . . . . . . . . . . 6
1.4 Mul ispec al Image P ocessing . . . . . . . . . . . . . . . . . . 6
2 FPGA Applica ions in space 9
2.1 SingleE en E ec s......................... 9
2.2 SEU de ec ion and mi iga ion . . . . . . . . . . . . . . . . . . . 10
2.3 SEU Mi iga ion App oaches . . . . . . . . . . . . . . . . . . . . 11
2.3.1 On-chip de ec ion . . . . . . . . . . . . . . . . . . . . . . 11
2.3.2 Ex e nal de ec ion . . . . . . . . . . . . . . . . . . . . . 11
2.3.3 Wa chdogs.......................... 11
2.3.4 Dual and T iple Module Redundancy . . . . . . . . . . . 12
2.3.5 Locks ep A chi ec u e . . . . . . . . . . . . . . . . . . . 12
3 Video Analysis: T acking objec s 13
3.1 Image Digi iza ion . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 P e-p ocessing............................ 16
i
1.4. Mul ispec al Image P ocessing 6
many yea s, howe e enhanced ision sys ems ha e been ce i ied o ci il a i-
a ion less han 15 yea s ago.
1.3.4 Image S abiliza ion
Came as moun ed in mo ing objec s o ehicles ecei e pa o his mo emen
mainly as ib a ion. E en hough physical solu ions such as shock abso be s
p o ide a good noise educ ion, some ideo p ocessing is needed o ob ain a
s able image. This is usually pe o med by FPGA and ASIC solu ions. The
p ocessing uni needs o ind he mo emen ec o om he ames o he ideo
s eam and adjus each ame consequen ly[4][5].
Ai c a s can mo e eely on he 3 dimensional space, unlike land and sea
ehicles. This adds ano he no desi ed mo emen in he ou pu s eam: he
oll o a ion. Gimbals a e o en used o p o ide ai c a came as eedom o
mo emen bu usually only o e pan and il axis o eedom.
Video s abiliza ion can be ob ained in wo manne s: ob aining he o a-
ional ec o om he ames o using he ai c a ine ial na iga ion sys em
(INS) o ob ain he cu en o a ion and adjus he image o i .
1.4 Mul ispec al Image P ocessing
A mul ispec al image is one ha cap u es image da a a speci ic equencies
ac oss he elec omagne ic spec um. I p o ides in o ma ion no a ailable by
only exploi ing he isible egion o he elec omagne ic spec um[6]. Used
mainly o opog aphic s udy, i ’s become e y impo an in de ense and sci-
en i ic obse a ion.
Non- isible spec um imaging was i s used du ing he Vie nam Wa , when
colo in a ed image y was used o dis inguish a i icial ea u es, like camou-
lage, om ege a ion. This echnology led o he de elopmen o senso s
o exploi a wide ange in he elec omagne ic spec um which we e la e

1.4. Mul ispec al Image P ocessing 7
equipped in he Landsa sa elli es. Landsa p og am became he longes un-
ning en e p ise o acquisi ion o sa elli e image y o Ea h and has launched
eigh sa elli es so a (Landsa 6 ailed o each o bi ) and nowadays Landsa
7 and 8 a e s ill ac i e.
Figu e 1.2: Landsa 8
Mul ispec al senso s p oduce a la ge se
o images which ha e o be ansmi ed. Im-
ages need o be encoded and comp essed in
o de o achie e good ans e a es, and
o his pu pose FPGAs p o e o be use-
ul hanks o hei Single Ins uc ion Mul-
iple Da a se (SIMD) compu a ion capabil-
i ies[7].
Chap e 2
FPGA Applica ions in space
Apa om high compu a ional pe o mance and o he ad an ages al eady
discussed, FPGA econ igu abili y pe mi s upg ades a e launch ha makes
hem highly sui able o space applica ions. Fu he mo e, his lexibili y helps
sol ing mishaps du ing un ime which can be mo e di icul o sol e using
ASICs o CPUs.
2.1 Single E en E ec s
Elec onics main p oblem in space applica ions is he adia ion. When a
high-ene gy pa icle passes h ough he silicon subs a e o a de ice, cha ged
pa icles a e c ea ed as he esul o sub-a omic pa icle collisions. These
pa icles a e gene a ed by an ioniza ion ail along he pa h o he incoming
pa icle and can in e e e wi h he no mal beha io o an elec onic ci cui [8].
The dis up ions p o oked by adia ion a e known as Single E en E ec s. De-
pending o he se e i y, wo kind o e o s can be iden i ied: Ha d and So
E o s.
So e o s a e eco e able, bu he sys em may need o be powe -cycled o
ini ia e a eco e y p ocedu e. Th ee ypes o so e o s can be iden i ied[9]:
Single-e en ansien s (SETs) Occu s when a high-ene gy pa icle im-
pac s a combina o ial pa h o a de ice and can induce a ol age/cu en
9
2.2. SEU de ec ion and mi iga ion 10
spike. I can p opaga e o he es o he ci cui .
Single-e en upse s (SEUs) These a e he esul o high-ene gy pa icles
causing a change in he s a e o a memo y elemen (SRAM, lip- lop, o
la ch). These a e he mos common SEE in a ionics applica ions.
Single-e en unc ion in e up s (SEFIs) They a e dis up ions o no -
mal de ice ope a ion. These ypes o e ec s al e he unc ionali y o
he ci cui and ypically equi e econ igu a ion/ ese o powe cycling
o eco e y.
SEE can also cause e y a e ha d e o s, which can be pe manen . FPGAs
a e mainly suscep ible o Single E en Bu nou whe e he ol age/cu en
spike p oduced by a high ene gy pa icle can p o oke physical damage o he
componen s o he ci cui .
2.2 SEU de ec ion and mi iga ion
FPGAs use memo y bo h in use logic (bulk memo y and egis e s) and in
Con igu a ion Random Access Memo y (CRAM) and hese memo ies, along
wi h lip- lops, can be upse by adia ion. CRAM con igu es all logic and ou -
ing in he FPGA; i an SEU s ikes a CRAM bi , he e ec can be se e e i i
a ec s c i ical logic in e nal signal ou ing (such as a lookup able bi )[10].
Block RAMs can be p o ec ed wi h e o -co ec ing code (ECC) and pa i y
schemes. FPGA con igu a ion memo y, howe e , canno be di ec ly p o ec ed
in he same manne as block memo y ia ECC o pa i y checks. SEU de-
ec ion echniques ha moni o de ice con igu a ion memo ies a e ecommen-
ded. Some space-g ade FPGAs include buil -in con igu a ion memo y e o
de ec ion, using ECC, bu mo e ecen ly, he use o lash memo ies has been
p oposed as an al e na i e, since hey need a much highe cha ge o discha ge
he loa ing ga e and swi ch s a e.
2.3. SEU Mi iga ion App oaches 11
2.3 SEU Mi iga ion App oaches
Manu ac u e s de elop adia ion ha dened space-g ade FPGAs o coun e meas-
u e SEUs adding physical p o ec ion. In addi ion, o he design measu es can
be aken:
2.3.1 On-chip de ec ion
FPGA manu ac u e s o e IP co es o mi iga e SEUs, moni o ing and epai ing
FPGAs con igu a ion memo y. On-chip p ocessing is au onomous: he FPGA
de ice de e mines whe he i is a ec ed by an SEU, wi hou needing ex e nal
logic. These co es ha e he abili y o de ec he sensi i i y o he ailu e
and asse an e o signal so he sys em can p o ide an app op ia e esponse
acco ding o i s se e i y.
2.3.2 Ex e nal de ec ion
SEU p ocessing IP co es can be con igu ed o use an ex e nal p ocesso . An
ex e nal CPU ecei es an in e up eques signal when he FPGA de ec s
a SEU. The CPU hen eads he E o Message Regis e and pe o ms he
sensi i i y lookup. This sys em ees up FPGA memo y space and con igu able
logic.
2.3.3 Wa chdogs
Wa chdogs a e special-pu pose ha dwa e modules a ached o he p ocesso .
They ha e limi ed impac on he pe o mance o he sys em bu hey may
equi e special de elopmen e o s a he so wa e le el in i s managemen .
These ime s moni o he con ol- low execu ion, he da a accesses pa e ns
and pe o m consis ency checks, while le ing he so wa e unning on he
p ocesso mos ly un ouched.

2.3. SEU Mi iga ion App oaches 12
2.3.4 Dual and T iple Module Redundancy
These solu ions a e e y use ul when sys em down ime is c i ical. In T iple
Module Redundancy (TMR) h ee iden ical ins ances o he ha dwa e a e un
and hei ou pu s a e p ocessed by a o ing sys em o p oduce a single ou pu .
I any o he h ee ins ances ails due o an SEU, he o he wo can co ec
and mask he e o .
This app oach implies a penal y in bo h a ea and powe consump ion, bu i
is by a he bes a ailable al e na i e o p o ec he p og amable logic agains
SEU.
Since in Dual Module Redundancy a disc epancy is no easily sol ed by
o ing, hese sys ems usually wo k in a mas e -sla e con igu a ion. The sla e
wo ks as a ho -s andby o he mas e . In case he mas e ails, he sla e is
eady o con inue execu ion as a backup.
2.3.5 Locks ep A chi ec u e
In a Locks ep A chi ec u e, wo sys ems a e synch onized o s a om he
same s a e and bo h ecei e he same inpu s. The e o e he s a e o bo h
sys ems should be equal a e e y clock cycle unless an abno mal condi ion
occu s[11]. Consis ency checks a e pe o med pe iodically, ei he by ime o
when he execu ion eaches a miles one.
When he s a es di e due o an e o , he execu ion mus be hal ed and
es a ed. Since a es a om he beginning is highly expensi e, checkpoin s
a e used o keep a copy o an e o - ee s a e in sa e s o age. Whene e a con-
sis ency check shows ha he esponse o he wo sys ems a e he same, hei
con ex 1is sa ed as a checkpoin in e o -p o ec ed memo y. I he consis -
ency check ails, a ollback ope a ion mus be pe o med, es o ing he p e ious
con ex o a checkpoin and he execu ion is esumed.
1All in o ma ion needed o es o e he sys em o a alid s a e
Chap e 3
Video Analysis: T acking objec s
Among all he FPGA applica ions o mode n ci il and mili a y a ia ion, as
well as o space equipmen , a i icial ision was chosen o expand on in his
p ojec . I bene i s eno mously om FPGA ea u es like pa allelism and high
compu ing powe o p o ide eal ime ideo analysis.
In his p ojec , we will ocus on an applica ion o iden i y objec s in a ideo
aken om a mo ing came a. The ideo had o be downscaled and immed
due o compu e pe o mance es ains.
Mode n se ial p ocesso s a e able o pe o m some o he p ocessing e-
qui ed o his applica ion wi h low la ency, bu hey a e no e y e icien and
ha e ouble keeping an a o dable la ency when in oducing high quali y ideo
like cu en s anda d 1080p1a 60 ames pe second. Wi h cu en endency
o inc ease e ical esolu ion up o 4K pixels, se ial p ocesso s a e no a good
solu ion o ideo p ocessing and analysis. FPGAs on he o he hand can
be p og ammed o pe o m pa allel, pixel-wise ope a ions o e a ame bu e
which la ency is o ba ely a ew clock cycles, allowing also pipelining.
A i icial ision is composed o many s ages:
•Image Digi aliza ion
11920 pixels in wid h and 1080 pixels in heigh ames, wi h p og essi e scan
13
3.1. Image Digi iza ion 14
•P e-p ocessing
•Segmen a ion
•Rep esen a ion
•Fea u e ex ac ion
•Classi ica ion and iden i ica ion
In his p ojec , he p e-p ocessing s age will be explained in dep h, along
wi h some algo i hms used in i , since i is he phase ha mos bene i om
FPGAs capabili ies. O he s ages will be analyzed as well in a mo e heo e ical
app oach.
3.1 Image Digi iza ion
An image is an op ical ep esen a ion o one o many objec s illumina ed by
one o mo e sou ces o adia ion ( isible ligh , x- ay, ul asonic, in a- ed, e c.).
Pa o his adia ion is abso bed by he objec and he es is e lec ed, de-
pending o he physical-chemical cha ac e is ics o he objec .
The e is no image cap u ing sys em as p ecise as he human (o animal)
isual sys em. F om an image in he eal wo ld, he i s s ep in digi izing is
an op ical sys em, usually o med by a se o lenses, which ac s as a low-pass
il e emo ing high equencies (de ails).
Nex s ep is cap u ing he image i sel using a senso . Common senso s
nowadays use CMOS (Complemen a y Me al-Oxide-Semiconduc o ) and CCD
(Cha ge-Coupled De ices) echnology. They a e composed by an a ay o
pho o-sensi i e elemen s which ans o m ligh in ensi y o an elec ic signal.
The quan i y o hese elemen s pe su ace uni de ines he esolu ion o he
images.
3.1. Image Digi iza ion 15
Figu e 3.1: Baye Pa -
e n
The pho o-sensi i e elemen s can only pe cei e he
in ensi y o he ligh , which would gene a e a g ay-
scale pic u e. In o de o sepa a e colo s, a il e mus
be applied be o e he senso so ha i only eads he
in ensi y o ha colo in pa icula . The mos used
app oach nowadays is a Baye il e mosaic. I is a
colo il e a ay o a anging ed, g een and blue colo il e s on a squa e g id
o pho osenso s.
A las laye o ha dwa e is needed o con e hese analog signals o a
digi al alue. This analog o digi al con e e pe o ms quan iza ion o he
inpu , hence in oducing some e o in he con e sion. The esolu ion o he
con e e indica es he numbe o disc e e alues i can p oduce o e he ange
o analog alues which in his case ep esen s he in ensi y o he colo .
As a esul o his con e sion, an N×Mma ix o in ege o eal numbe s
is ob ained. Each elemen o his ma ix is called a pixel. I he image is
colo sepa a ed i becomes a 3-dimensional a ay, wi h one laye o each colo
(usually h ee).
I ’s easy o calcula e he equi ed space o s o e an image om he e. The
gene al o mula is:
Sizeby es =Wid h ×Heigh ×Colo Deepness ×NColo s/8
Fo a aw 1080p image wi h 10 bi colo deepness he size is 1290 ×1080 ×
10 ×3/8 = 7776000 by es o 7.77 Mb. A a a e o 60 ames pe second, each
second 466.56 Mb o da a a e gene a ed. Huge bandwid h is needed in o de
o anspo such amoun o da a, hence comp ession and encoding a e usually
pe o med. So wa e solu ions a e widesp ead o gene al public bu encoding
pe o mance in a se ial p ocesso is a he ine icien . On he o he hand, com-
me cial IP co es o FPGAs and ASICs2ha e a e y good pe o mance, wi h
2Applica ion-Speci ic In eg a ed Ci cui
3.2. P e-p ocessing 22
Figu e 3.7: F ame om igu e 3.6 a e his og am equaliza ion
5. Rescan he image and w i e an ou pu image wi h g ay le els gq, w i ing:
gq=T[gp]
The esul o his og am equaliza ion o e he ame om igu e 3.6 can be
seen in he igu e 3.7. The g ay le els ha e been sp ead along he dynamic
ange. Being a disc e e en i onmen , his is he bes esul ob ainable. The
Ma lab code can be consul ed in he lis ing 2. His og am equaliza ion is a
global ope a ion ha equi es eading he whole image and s o e i in a ame
bu e o ope a e o e i . This b eaks he pipeline and adds a la ency o 1
ame pe second o he p ocess.
3.2.4 Noise educ ion
Usually, images ha e whi e noise, wi h ze o mean and ini e a iance. Noise
educ ion helps imp o ing he esul s o he la e image p ocessing, such as
bo de ecogni ion. The app oach o emo e his noise is by low-pass il e s[14].
The mos used a e:
Median il e
Al hough he same windowing p ocess is used as in a con olu ion, median il e
doesn’ pe o m any sum o he neighbo pixels. In s ead, he median is he
numbe sepa a ing he highe hal o he neighbo elemen s om he lowe

3.3. Segmen a ion 23
hal . The median il e is a nonlinea digi al il e ing echnique.
I needs a lo o compu a ional e o since he median o he window o each
elemen o he image has o be calcula ed. Fo small o mode a e le els o
noise, he median il e is demons ably be e han o he il e s a educing
noise and p ese ing bo de s.
Mean il e
1/9 1/9 1/9
1/9 1/9 1/9
1/9 1/9 1/9
Figu e 3.8: Mean il e ke nel
This il e compu es he a e age o all he
pixels o a window cen e ed on he ou pu
pixel. I is easily implemen ed as a con olu-
ion using ke nels such as in igu e 3.8. How-
e e , his il e is e y agg essi e wi h he
bo de s despi e i s gain in pe o mance.
Bo h median and mean ke nels don’ need o be squa e, al hough hey a e he
mos used. The size is usually 3×3,5×5, e c. Bu i ’s been demons a ed
ha i he size is e y big, ha is 7×7o 9×9, he esul s a e no good. In
s ead, i he image is e y noisy, i ’s be e o apply smalle ke nels in cascade,
ha is, apply he same il e o he esul o a p e ious applica ion.
Gaussian blu
This il e uses a Gaussian unc ion, wi h a bell shape, ha is less agg essi e
o he bo de s, since he cen e o he ke nel will a enua e mo e he noise
han he pe iphe al elemen s. Howe e , he use o exponen ials, and complex
di isions in he gaussian unc ion, makes i unsui able o es ing wi h simple
FPGAs.
3.3 Segmen a ion
The goal o image segmen a ion is o sepa a e he in e es ing objec s om
he es , conside ed as backg ound. Segmen a ion is usually conside ed as a
p ocess o classi ying objec s in an image. The le el o segmen a ion depends
3.3. Segmen a ion 24
on he applica ion.
In his case, we a e analyzing ideos aken om a mo ing came a (ano he
plane) and hence backg ound iden i ica ion and sub ac ion is no an easy
ask. In s ead, he ames mus be ca e ully segmen ed and h esholded. An
ad an age o using FPGAs ope a ing in eal ime is ha he algo i hms can
be eadjus ed wi h eedback so h esholds and dep h o segmen a ion can be
adap ed.
3.3.1 Bo de De ec ion
A bo de can be de ined as a signi ican change in he in ensi y o he pixels o a
egion o an image, o as a high g adien on a poin . Bo de de ec ion consis s
o iden i y which pixels can be conside ed pa o a bo de . The knowledge o
his poin s allows he cons uc ion o he bo de s and hence he bounding o
he on ie s o he egions on an image.
Bo de de ec ion can yield in o ma ion abou he di ec ion o he bo de ,
i ’s in ensi y ( he di e ence in con as ) o i ’s di ec ion (which pa is b igh e
han he o he ). In addi ion, as image o ma ion is no a pe ec p ocess, bo de
de ec ion has o deal wi h noise o agmen a ion (some pa s o he con ou
a e los ).
In o de o help he de ec o , a noise educ ion p ocess should be applied
p e iously. A median il e will be applied be o e he bo de de ec ion al-
go i hm o he examples shown in he nex sec ions.
Sobel Ope a o
I is one o he classic echniques in bo de de ec ion based in compu ing
a disc e e app oxima ion o he g adien o he g ayscale image. I c ea es
an image ha emphasizes edges and ansi ions. A each pixel, he alue
o he ou pu is an app oxima ion o he no m o he g adien ec o o he
inpu pixel. The Sobel ope a o is based on con ol ing he image wi h a
3.3. Segmen a ion 25
-1 0 1
-2 0 2
-1 0 1
-1 -2 -1
0 0 0
1 2 1
Figu e 3.9: Ve ical and ho izon al ke nels o he Sobel ope a o
Figu e 3.10: Le , bo de de ec ion wi h Sobel ope a o o e he ame om
igu e 3.6; igh wi h median il e applied be o e bo de de ec ion.
small and in ege alued il e in ho izon al and e ical di ec ion which can
be implemen ed in an FPGA wi h he design om he igu e 3.3.
The e a e wo ke nels o he Sobel ope a o , one o e ical bo de s and
o he o ho izon al as shown in igu e 3.9. Addi ionally, o he il e s can be
c ea ed o iden i y diagonal lines by o a ing hese il e s. Bo h il e s mus be
applied o he o iginal image, gene a ing wo ames, so he eal ou pu mus
be he mean o he wo. Ideally, he oo mean squa e should be used, bu in
in an FPGA en i onmen is easie o calcula e he mean o wo alues in s ead
o calcula e a squa e oo .
Laplacian ope a o
Ano he classic app oach o bo de ecogni ion is by using he second de i -
a i e. The Laplacian ope a o is widely used o accen ua e a bo de wi hou
aking in o accoun i s di ec ion. The disc e e e sion o his il e can be
seen in igu e 3.11. Howe e , he second de i a i e is e y sensi i e o noise,
and so usually i is used oge he wi h a Gaussian low-pass il e . Since he
con olu ion ope a ion is associa i e, he Laplacian and Gaussian il e s can be
con ol ed be o ehand and hen con ol e his hyb id il e wi h he image o
3.3. Segmen a ion 26
0 1 0
1 -4 1
0 1 0
0.5 1 0.5
1 -6 1
0.5 1 0.5
Figu e 3.11: Two e sions o Laplacian il e s. The one in he igh includes
diagonal lines
Figu e 3.12: Laplacian ope a o o e he ame om igu e 3.6
ob ain he bo de s.
Du ing he es s pe o med wi h Ma lab he Laplacian ope a o showed
good esul s iden i ying co ne s ( igu e 3.12), bu no so good in he in eg i y
o he bo de whe e Sobel had be e esul s. Hence he chosen ope a o was
Sobel wi h a p e ious (double) median il e smoo hing. I s Ma lab code can
be consul ed a lis ing 3.
3.3.2 Objec Recogni ion
An ad an age o using Sobel ope a o s o de ec bo de s is ha hey e u n
he in ensi y o he bo de , allowing h esholding o disca d low-g adien ans-
i ions ha can be noise o backg ound while enhancing objec s. The h eshold-
ing ope a ion can be easily implemen ed in a pipeline since i is a punc ual
ope a ion. A h eshold Tis he alue applied o a ans o ma ion o inpu
3.4. Fea u e Ex ac ion 27
ame (x, y)in o ou pu g(x, y)as in he o mula:
g(x, y) = 


1i (x, y)≥T
0i (x, y)< T
FPGAs allow his h eshold o be dynamically calcula ed and adjus ed in
eal ime so i mee s he equi emen s o he applica ion. Ma lab simula ion
can be ound in lis ing 4.
The ame is now a cloud o bo de poin s. A high densi y o hese poin s
in a gi en a ea can be assumed as a sepa a ed objec , hence applying a mean
il e wi h a big enough window can yield he densi y o bo de poin s in he
a ea su ounding each pixel as a ac ion. Applying a h eshold o he esul ing
ame wi h he pe cen age alue ha could be conside ed an objec . An special
Ma lab unc ion (lis ing 5) was c ea ed o pe o m hese wo ope a ions and
yield a bina y image ha sui s he nex s eps.
3.4 Fea u e Ex ac ion
3.4.1 Connec ed-componen labeling
Figu e 3.13: Al eady
p ocessed neighbo s (8-
connec ion)
Connec ed-componen labeling is an algo i hm
ha labels subse s o connec ed componen s
based on a gi en heu is ic in a bina y im-
age. This se es o iden i y and sepa a e
he clouds o bo de s gene a ed in he p e ious
s ep.
The classic algo i hm is pe o med in wo passes.
The algo i hm examines he al eady p ocessed neigh-
bo s o each pixel shown in igu e 3.13 and de e mines which label o assign
acco ding o he p ocedu e de ined by Milan Sonka[13] as ollows:
1. Fi s pass: Sea ch he en i e image Rby ows and assign a non-ze o

3.4. Fea u e Ex ac ion 28
alue o each non-ze o pixel R(i, j). The alue is chosen acco ding
o he labels o he pixel’s neighbo s.
•I all he neighbo s a e backg ound pixels (wi h pixel alue ze o),
R(i, j)is assigned a new (and as ye ) unused label.
•I he e is jus one neighbo ing pixel wi h a non-ze o label, assign
his label o he pixel R(i, j).
•I he e is mo e han one non-ze o pixel among he neighbo s, assign
he label o any one o he labeled pixel. I he labels o any o he
neighbo s di e (label collision), s o e he label pai as being equi-
alen . Equi alence pai s a e s o ed in a sepa a e da a s uc u e—
an equi alence able.
2. Second pass: All o he egion pixels we e labeled du ing he i s pass,
bu some egions ha e pixels wi h di e en labels (due o label collisions).
The whole image is scanned again, and pixels a e e-Iabeled using he
equi alence able in o ma ion ( o example, wi h he lowes alue in an
equi alence class).
Label collisions a e p e y common. They a e p oduced when he blob has
an Ushape. In he i s pass he algo i hm will de ec each op pa o he U
as di e en labels and when i eaches he bo om he e a e 2 di e en labels
in he neighbo s. This con lic s a e sol ed du ing he second pass. Hence, his
algo i hm is highly ine icien since i needs o pe o m wo passes o e each
ame o co ec ly de ec all objec s and needs o use an in e media e ame
bu e .
Some in es iga o s ha e p oposed implemen a ions o his algo i hm in
eal- ime using FPGAs, exploi ing hei capabili ies in pa alleliza ion and
pipelining. Donald G. Bailey and Ch is ophe T. Johns on i s app oach
[15] a oided he need o bu e ing he image be ween passes by pe o ming
jus one pass bu had p oblems wi h wo s case scena ios whe e he numbe
o labels gene a ed p io o me ge was huge. In he nex i e a ion[16], his
p oblem was sol ed by eusing he labels. One las app oach implemen ed he
3.5. Rep esen a ion 29
Figu e 3.14: Objec ecogni ion plo ed o e o iginal ideo
ga he ing o ea u e da a o each egion in pa allel wi h labeling, enabling a
single s eamed pipeline implemen a ion[17].
This algo i hm elies on lookup ables o me ging, and so adap ing he al-
go i hm o Ma lab code is no an easy ask. Howe e , Ma lab o e s a unc ion
ha labels he egions o a bina y image, and was used in lis ing 6.
3.5 Rep esen a ion
Once he ames ha e all hei impo an objec s labelled, a good way o dis-
play his da a is by plo ing i o e he o iginal ideo, since he p ocessed one
no longe holds he isual ea u es o he o iginal.
The labeled pixels o each ame ha e o be sea ch o sepa a e hei egions
and ob ain hei in o ma ion such as maximum and minimum on bo h axis
and/o hei cen oid. This da a is la e used o gene a e ec angles ha will
show he iden i ied objec s o he ame.
While he in o ma ion ga he ing can be pe o med in he pipeline, he
g aphics gene a ion can’ . Taking in o accoun he ac ha hey a e applied
o e he o iginal ame, he plo ing doesn’ need o wai o he ame o be
3.6. Final esul 30
Figu e 3.15: Sequence o s eps
comple ely ou o he pipeline.
In he Ma lab unc ion in lis ing 7, he Visual lib a y is used o gene a e
he g aphics, o simpli ica ion sake. The inal esul can be seen in igu e 3.14.
The p ocess is able o ecognize objec s, bu i needs eadjus men in eal ime
o cap u e mos o he impo an da a.
3.6 Final esul
The sequence o s eps in Ma lab can be ound in Lis ing 8. Execu ing he
p ocedu e on a compu e akes a couple o minu es while he delay on an
FPGA should be o abou 1-2 ames. Hence, he la ency in se ial compu e s
inc eases linea ly wi h he leng h o he ideo, making he p ocess una o dable
in a s eam, while he pipelined algo i hm on an FPGA has a ixed la ency.
3.6. Final esul 31
Figu e 3.16:
Al e na i e o His o-
g am Equaliza ion
Pa allel calib a ion can be in oduced in he
h esholding and objec loca ion s eps when imple-
men ing he algo i hm in he FPGA as can be seen
in igu e 3.15. The majo delay is p oduced in he
his og am equaliza ion s ep because i needs a ame
bu e o ope a e, hence s alling he pipeline. How-
e e , he de ec ion s ep can be pa allelized, eading
all inpu pixels in he s eam and calcula ing he
lookup able. The g ey alue co ec ion can hen be
execu ed wi h a la ency o one ame, delaying only
his s ep in s ead o he whole pipeline. Luminosi y
doesn’ change suddenly in open a eas so he delay
is a o dable.
The ou pu ideo gene a ed in his wo k can be seen in h ps://you u.
be/nqsTOEPAwyo
Bibliog aphy 38
[13] Milan Sonka. Image P ocessing, Analysis, and Machine Vision. 2008.
[14] Robe o Rod iguez Mo ales and Juan Humbe o Sossa Azuela. P oces-
amien o y Análisis Digi al de Imágenes. 2011.
[15] Donald G. Bailey and Ch is ophe T. Johns on. “Single Pass Connec ed
Componen s Analysis”. In: P oceedings o Image and Vision Compu ing
(2007).
[16] Ni Ma, Donald G. Bailey and Ch is ophe T. Johns on. “Op imised
Single Pass Connec ed Componen s Analysis”. In: ICECE Technology,
2008. FPT 2008. In e na ional Con e ence on (2008).
[17] Donald G. Bailey, Ch is ophe T. Johns on and Ni Ma. “Connec ed com-
ponen s analysis o s eamed images”. In: Field P og ammable Logic and
Applica ions, 2008. FPL 2008. In e na ional Con e ence on (2008).

Appendix: Sou ce Code
Lis ing 1: G ayscale Con e sion
1 unc ion [ idg ay ] = id2g ayscale ( id )
2 idg ay = uin 8 ( ze os(size ( id ,1) , size( id ,2) , size (
id ,4) ) ) ;
3 o i =1: s i z e ( id , 4)
4 idg ay ( : , : , i ) = id ( : , : , 1 , i ) ∗0.25 + id ( : , : , 2 , i
)∗0.5 + id ( : , : , 3 , i ) ∗0.125;
5end;
6 idg ay=squeeze ( idg ay ) ;
7end
Lis ing 2: His og am Equaliza ion
1 unc ion [ ideq ] = his Eq id ( id )
2 ideq=uin 8 ( ze os(s i z e ( id ) ) ) ;
3
4[M, N, T] = size ( id ) ;
5G = 256;
6 o =1:T
7%Scan e e y pixel and inc emen he ele an
membe o H−− i pixel p has
8%in ensi y gp , pe o m
9H = uin 32 ( ze os(1 , G) ) ;
10 o i = 1:M
11 o j = 1:N
39
Bibliog aphy 40
12 gp = id ( i , j , ) ;
13 Temp = H(gp+1)+1; % Adjus gp o go om
1 o G, no 0 o G−1
14 H(gp+1) = Temp;
15 end
16 end
17
18 %Fo m he cumula i e image his og am Hc and
c ea e he lookup able o s ep 4:
19 Hc = uin 32 ( ze os(1 ,G) ) ;
20 T = uin 32(ze os(1 ,G) ) ;
21 Hc(1) = H(1) ;
22 T(1) = ound (((G−1)/(N∗M) ) .∗H(1) ) ;
23 o p = 2:G
24 A = Hc(p −1) + H(p) ;
25 Hc(p) = A;
26 B = ound (((G−1)/(N∗M) ) .∗Hc(p) ) ;
27 T(p) = B;
28 end
29
30 %Rescan he image and w i e an ou pu image wi h
g ay−l e e l s gq
31 o i = 1:M
32 o j = 1:N
33 gp = id ( i , j , ) ;
34 Temp = T(gp+1) ; % Adjus gp o go om 1
o G, no 0 o G−1
35 ideq ( i , j , ) = Temp;
36 end
37 end
38 end
39 end
Bibliog aphy 41
Lis ing 3: Bo de de ec ion wi h Sobel ope a o , smoo hed wi h double median
il e
1 unc ion [ bVid ] = idBo de s ( id )
2%C ea ion o he wo Sobel i l e s
3hSobel= [−1−2−1; 0 0 0; 1 2 1 ] ;
4 Sobel= [−1 0 1; −2 0 2; −1 0 1 ] ;
5
6%Memo y alloca ion o he bu e s
7bVidBu = ze os(size( id ( : , : , 1 ) ) ) ;
8bVidH = ze os(s i z e ( bVidBu ) ) ;
9bVidV = ze os(s i z e ( bVidBu ) ) ;
10
11 o i =1: s i z e ( id , 3)
12 %Double applica ion o he median i l e o
smoo h he ame
13 bVidBu ( : , : , i ) = uin 8 ( med il 2 ( id ( : , : , i ) ) ) ;
14 bVidBu ( : , : , i ) = uin 8 ( med il 2 ( bVidBu ( : , : , i )
) ) ;
15 %Con olu ing o bo h ke nels wi h he inpu
ame.
16 %Ma lab equi es con 2 pa ame e s o be o ype
single.
17 %The ’same ’ pa ame e es a b lishe s ha he
ou pu ame i s he same s i z e as he inpu
18 bVidV ( : , : , i ) = uin 8 ( con 2( s ingle ( bVidBu ( : , : , i
) ) , Sobel , ’same ’ ) ) ;
19 bVidH ( : , : , i ) = uin 8 ( con 2( s ingle ( bVidBu ( : , : , i
) ) , hSobel , ’same ’ ) ) ;
20 end;
21 bVid=uin 8 (( bVidH+bVidV) ./2) ;
22 end
Bibliog aphy 42
Lis ing 4: Th esholding
1 unc ion [ idTh es ] = idTh eshold ( id , h eshold )
2%Memo y alloca ion o he esul ing ame
3 idTh es = l o g i c a l ( ze os(s i z e ( id ) ) ) ;
4
5 o i = 1: size( id ,3)
6 idTh es ( : , : , i )=(im2bw( id ( : , : , i ) , h eshold ) ) ;
7end;
8%Re u n ma ix i s con e ed o uin 8 o se e as
inpu o nex s eps
9 idTh es = uin 8 ( idTh es .∗255);
10 end
Lis ing 5: Objec de ec ion
1 unc ion [ idO ] = loca eObjec s ( idI , h eshold )
2
3mean = (1/121)∗( ones (11 ,11) ) ;
4 idBu = uin 8(ze os(size( idI ) ) ) ;
5 idO = l o g i c a l ( ze os(s i z e ( idBu ) ) ) ;
6
7 o i =1: s i z e ( idI ,3)
8 idBu ( : , : , i ) = uin 8 ( con 2( s i ngle ( idI ( : , : , i ) )
,mean ,’same ’ ) ) ;
9 idO ( : , : , i )=(im2bw( idBu ( : , : , i ) , h eshold ) ) ;
10 end
11 end
Lis ing 6: Connec ed-Componen Labeling
1 unc ion [ idO , nObjec s ] = cclVid ( idI )
2nObjec s = uin 8 ( ze os(1 , size ( idI ,3) ) ) ;
3 idO = uin 8 ( ze os(s i z e ( idI ) ) ) ;
4 o i =1: s i z e ( idI ,3)
5%The Connec ed Componen Labeling algo i hm i s
Bibliog aphy 43
e y u n e i c i e n o implemen in Ma lab due
o he a c ha Ma lab i s no p epa ed o
wo k wi h complex da a s uc u es l i k e lookup
ables , s acks , e c .
6%Howe e , Ma lab o e s a unc ion ha pe o ms
labelin g on bina y images
7[ idO ( : , : , i ) , nObjec s ( i ) ] = bwlabel ( idI ( : , : , i ) )
;
8end
9end
Lis ing 7: Objec s ep esen a ion on ideo
1 unc ion [ idO ] = plo Video ( idRGB , idLabeled ,
nObjec s )
2%In o de o plo i g u es in Ma lab , an
shapeInse e objec , included in he ision
lib a y , i s needed
3shapeInse e = ision . ShapeInse e ( ’LineWid h ’ ,2 , ’
Bo de Colo ’ ,’Cus om ’ ,’Cus omBo de Colo ’ , [255
0 0]) ;
4 idO=uin 8 ( ze os(size ( idRGB) ) ) ;
5
6 o =1: s i z e ( idLabeled ,3)
7%I n i i a l i z e he ou pu wi h he o iginal , colo
ideo
8 idO ( : , : , : , ) = idRGB ( : , : , : , ) ;
9[ y , x]=ndg id (1: s i z e ( idLabeled ,1) ,1: size (
idLabeled ,2));
10 %I e a e o e he de ec ed " blobs " o each ame
11 o k=1: nObjec s ( )
12 %calcula e he max and min dimensions o
plo ec angles
13 maxx=max(y( idLabeled ( : , : , )==k) ) ;

Bibliog aphy 44
14 minx=min(y( idLabeled ( : , : , )==k) ) ;
15 maxy=max(x( idLabeled ( : , : , )==k) ) ;
16 miny=min(x( idLabeled ( : , : , )==k) ) ;
17 %De ine he i n i i a l poin s and dimension o
he ec angle
18 ec angle = in 32 ( [ miny , minx , maxy−miny ,
maxx−minx ] ) ;
19 %D aw he ec angle
20 idO ( : , : , : , ) = s ep ( shapeInse e , idO
( : , : , : , ) , ec angle ) ;
21 end
22 end
23 end
Lis ing 8: Sequence o s ages o ideo p ocessing
1load(’mo ’ ) ;
2g ay = id2g ayscale (mo ) ;
3eq = his Eq id(g ay ) ;
4bo de s = idBo de s ( eq ) ;
5bo de sTh es = idTh eshold ( bo de s , 0.35) ;
6obj = loca eObjec s ( bo de sTh es , 0.15) ;
7[ labeled , nObjec s ] = cclVid ( obj ) ;
8ou pu = plo Video (mo , labeled , nObjec s ) ;
9implay ( ou pu ) ;