Aproximación a la implementación de aplicaciones aero-espaciales en hardware

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 ) ;