Efficient Algorithms for Large-Scale Image Analysis [Elektronische Ressource] / Jan Wassenberg. Betreuer: Peter Sanders

Jan Wassenberg

Description

Efficient Algorithms forLarge-Scale Image Analysiszur Erlangung des akademischen Grades einesDoktors der Ingenieurwissenschaftender Fakultät für Informatikdes Karlsruher Instituts für TechnologiegenehmigteDissertationvonJan Wassenbergaus KoblenzTag der mündlichen Prüfung: 24. Oktober 2011Erster Gutachter: Prof. Dr. Peter SandersZweiter Prof. Dr.-Ing. Jürgen BeyererAbstractThe past decade has seen major improvements in the capabilitiesand availability of imaging sensor systems. Commercial satellitesroutinely provide panchromatic images with sub-meter resolution.Airborne line scanner cameras yield multi-spectral data with aground sample distance of 5 cm. The resulting overabundance ofdata brings with it the challenge of timely analysis. Fully auto-mated processing still appears infeasible, but an intermediate stepmight involve a computer-assisted search for interesting objects.This would reduce the amount of data for an analyst to examine,but remains a challenge in terms of processing speed and workingmemory.This work begins by discussing the trade-offs among the varioushardware architectures that might be brought to bear upon theproblem. FPGA and GPU-based solutions are less universal andentail longer development cycles, hence the choice of commoditymulti-core CPU architectures. Distributed processing on a cluster isdeemed too costly.

Sujets

• Informatik

Informations

• Publié par: karlsruher_institut_fur_technologie
• Publié le: 01 janvier 2011
• Nombre de lectures: 59
• Langue: English
• Poids de l'ouvrage: 4 Mo

Extrait

agT

forithmsAlgorficientEf

AnalysisImageLarge-Scale

zurErlangungdesakademischenGradeseines

wissenschaftenIngenieurderDoktors

desderKarlsruherFakultätInstitutsfürInforfürTmatikechnologie

genehmigte

Dissertation

von

assenbergWJan

Koblenzaus

dermündlichenPrüfung:24.Oktober2011

ErsterGutachter:Prof.Dr.PeterSanders

ZweiterGutachter:Prof.Dr.-Ing.JürgenBeyerer

Abstract

andTheavpastailabilitydecadeofhasimagingseenmajorsensorimprosystems.vementsCommerinthecialcapabilitiessatellites
rAirboroutinelyneprlineovidescannerpanchrcamerasomaticyieldimageswithmulti-spectralsub-meterdatarwithesolution.a
grdataoundbringssamplewithitdistancetheof5challengecm.ofThertimelyesultingoanalysis.verabundanceFullyauto-of
mightmatedprinvolvocessingeastillcomputerappears-assistedinfeasible,searchbutforaninterinterestingmediateobjects.step
butThisrwemainsouldraeducechallengetheinamounttermsofofdataprforocessinganspeedanalystandtowexamine,orking
.ymemorhardwThisarwearorkbeginschitecturbyesthatdiscussingmightthebebrtrade-ofoughtfstoamongbeartheuponvariousthe
prentailoblem.longerFPGAdevandelopmentGPU-basedcycles,hencesolutionsthearechoicelessofuniversalcommodityand
deemedmulti-coretooCPUcostlyar.Wechitecturwilles.demonstrateDistributedtheprfeasibilityocessingonofaprclusterocessingis
2aerialhoursonimagesaofsingle100wkm×orkstation100kmwithareastwoatpr1mrocessorsesolutionandawithintotal
oftwelvecores.Becauseexistingapproachescannotcopewith
–suchfromdataamountsoaccessfdata,andeachsignalstageprofocessingthetoimageobjectprocessingextractionpipelineand
forfeaturemaximumcomputationperfor–mance.willhaWveetointrbeoducedesignednewfreffiomcientthegroundalgorithmsup
thatLetprousvidebeginusefulwithresultstheatmostfastertime-cspeedsriticalthantaskpre–theviouslyextractionpossible.
ofThisobjectstepiscandidatesnecessaryfrombecauseanimage,individualalsoknopixelswnasdonotprsegmentation.ovide
ableenoughmodelinforforthemationobjectsfortheinvscrolveseeninggroupingtask.Asimilarsimplepixelsbutrtogethereason-.
netwHigh-qualityorkflowandclusteringanisotropicalgorithmsdiffusionbasedareonfarmeantooshift,time-consuming.maximum

ix

prWeopertyintrofoduceavaoidingnewbothgraph-basedunder-andovalgorithmersegmentation.withtheItsimportantdistin-
guishingfeatureistheindependentparallelprocessingofimage
tileswithoutsplittingobjectsattheboundaries.Ourefficient
implementationtakesadvantageofSIMDinstructionsandout-
perforsimilarmsqualitymean.shiftbRecognizingyafactortheof50outstandingwhileprperforoducingmanceresultsofitsof
wemicrdeoarvelopchitecturitintoe-aawargenerale32-bitvirtual-memorintegerysortercounting,yieldingsortsubrthefastestoutine,
knownalgorithmforshared-memorymachines.
fultoBecausesuppresssegmentationsensornoise.groupsThetogetherBilateralsimilarFilterispixels,anitisadaptivhelp-e
smoothingkernelthatpreservesedgesbyexcludingpixelsthatare
distantinthespatialorradiometricsense.Severalfastapproxi-
highermation-dimensionalalgorithmsarespace.knoWwn,ee.g.accelerateconvthisolutionintechniqueadobyawnsampledfactor
ofimation14viaofthe3Dparallelization,Gaussvkernel.ectorizationTheandsoftwaareis73SIMD-friendlytimesasapprfastox-as
anexactcomputationonanFPGAandoutperformsaGPU-based
approximationbyafactorof1.8.
Physicallimitationsofsatellitesensorsconstituteanadditional
hurdle.Thenarrowmultispectralbandsrequirelargerdetectors
andFusingusuallybothhavdatasetsealoiswerterrmedesolutionpan-sharthanthepeningpanchrandimpromaticovesband.the
techniquessegmentationareduevulnerabletothetocoloradditionaldistortioncolorinforbecausemation.ofPremismatchesvious
efbetwfect,eenwethecomputebandsthespectraloptimalrsetesponseofbandwfunctions.eightsToforreacheduceinputthis
image.Ournewalgorithmoutperformsexistingapproachesbya
factorof100,improvesupontheircolorfidelityandalsoreduces
noiseinthepanchromaticband.
Becausethesemodulesachievethroughputsontheorderof
seTheveralubiquitoushundredMB/s,GDALthelibrarnextyisfarbottleneckslowertobethanaddrtheessedtheoriseticalI/O.

x

diskthroughput.Wedesignanimagerepresentationthatavoids
efficientunnecessaryasynchrcopying,onousandI/O.Thedescriberesultinglittle-knosoftwwnareistechniquesuptofor12
timesasfastasGDAL.Furtherimprovementsarepossibleby
compressingthedataifdecompressionthroughputisonparwith
theasymmetrictransferSIMDspeedscodecofathatdiskachiearravy.esaWecomprdevelopessionanoratiovelof0.5losslessfor
on16-bitasinglepixelscorande.rThiseachesisaboutdecompr100essiontimesthrasfastoughputsasof2lossless700MB/sJPEG-
2000Letandusnoonlywr20–60%eturntolargertheonextractedmultispectralobjects.satelliteAdditionaldatasets.steps
fordetectingandsimplifyingtheircontourswouldprovideuse-
fulinformation,e.g.forclassifyingthemasman-made.Toallow
softwannotatingarelarrasterizerge.imagesHigh-qualitywiththerantialiasingesultingpolyisachiegons,vwedebydevisederiv-a
ingoutperforthemsoptimalthepolynomialGupta-Sprlooullw-passalgorithmfilter.byOurafactorofimplementation24and
exceedsTheprtheeviouslyfillrateofadescribedmid-rangeprGPU.ocessingchainiseffective,but
electro-opticalsensorscannotpenetratecloudcover.Becausemuch
oftheearthssurfaceisshroudedincloudsatanygiventime,we
haveaddedaworkflowfor(nearly)weather-independentsynthetic
fromapertureuniforradarmly.Small,brightrhighly-regionsbeflectivyesubtractingobjectscaneachbedifferpixelsentiatedback-
grtheound,asymptoticestimatedfrcomplexityomtheofdarkestthisapprringoachsurrtoitsoundinglowit.erWeboundreduceby
AmeansofsophisticatedanewpipeliningalgorithminspirschemeedbensuryesRangethewMinimumorkingsetfitsQueries.in
cache,andthevectorizedandparallelizedsoftwareoutperforms
anFPGAimplementationbyafactorof100.
andTheseGPUresultssolutionschallengeenabletheconvsignificantentionalspeedupswisdomoverthatgeneral-FPGA
thepurloposewerCPUs.boundofBecausetheirallofcomplexitytheabo,vetheiralgorithmsusefulnesshaviserdecidedeached

xi

byconstantfactors.Itisthethesisofthisworkthatoptimized
softwarerunningongeneral-purposeCPUscancomparefavorably
inthisregard.Thekeyenablingfactorsarevectorization,paral-
lelization,andconsiderationofbasicmicroarchitecturalrealities
suchasthememoryhierarchy.Wehaveshownthesetechniquesto
beapplicabletowardsavarietyofimageprocessingtasks.How-
ever,itisnotsufficienttotunesoftwareinthefinalphasesofits
development.Instead,eachpartofthealgorithmengineeringcycle
–design,analysis,implementationandexperimentation–should
accountforthecomputerarchitecture.Forexample,noamount
ofsubsequenttuningwouldredeemanapproachtosegmentation
thatreliesonaglobalrankingofpixels,whichisfundamentally
lessamenabletoparallelizationthanagraph-basedmethod.The
algorithmsintroducedinthisworkspeedupsevenseparatetasks
byfactorsof10to100,thusdispellingthenotionthatsuchefforts
arenotworthwhile.Wearesurprisedtohaveimprovedupon
long-studiedtopicssuchaslosslessimagecompressionandline
rasterization.However,thetechniquesdescribedhereinmayallow
domains.otherinsuccessessimilar

xii

Acknowledgements

Iguidancesincerely–thankidentifyingmypradvisor,omisingProf.avPeterenuestoSanders,explorfore,proteachingviding
algorithmengineering,andsharingtheloreofcleveroptimizations.
Thankyou,Prof.Dr.-Ing.JürgenBeyerer,forreviewingthisthesis.
Lookingbackearlier,Ithankmyparentsfortheirloveandsup-
rport,esultingandforinteralloestinwingmecomputingaccesswtoasakindledTRS-80earlymicronatocomputerRandolph.The
Sconcerchool,ningaespeciallymodelbryDrocket.RobertsimulatorKir.chnerThanksstophysicsmysoccerassignmentcoach,
H.KillebrewBailey,forinstillingthespiritpracticehard,play
hard;noregrets!
Igratefullyacknowledgetheproductiveworkingenvironment
attheFGAN-FOMresearchinstitute,nowapartofFraunhofer
tianIOSB.WuttkeThanksfortointermyofestingficematesdiscussionsDominikoverPerlunchpeetandandSfruitfulebas-
administrativcollaboration;eRomymatters;PfeifmyfersuperandvisorAnjaDr.WBlancaniolfgangforhelpingMiddelmannwith
anddepartmentheadDr.KarstenSchulzforprovidingguidance
andthelatitudetoworkoninterestingproblems.
Thisthesisbuildsuponmachine-orientedgroundworklaidfor
thepleasur0eA.D.towstrategyorkwithgamethisprteamojectofstartingenthusiastic,in2002.Itself-motivhasbeenateda
volunteers,especiallyPhilipTaylor.
usefulIamtooltogratefulrtoead/writetheauthorsnearlyofanyGDALimageforfiledevforelopingmat.aThankstruly
toCharlesBloom,Prof.TanjaSchultzandDominikPerpeetfor
valuablefeedbackconcerningpartsofthiswork.
andImostapprofeciateall,themybelopatiencevedandSufen.Herunderstandingloveandofsupportfriends,meanfamilyso,
me.tomuch

xiii

Thisworkisdedicatedtothescientists/engineers/craftsmen
whobridgethegapbetweentheoryandpracticeofcomputing,
devisingsolutionsforpreviouslyinsurmountableproblemsand
teasingoutmaximumperformanceduetoadetailedunderstand-
ingoftheunderlyinghardware.Keeptheflameburning!
xiv

Contents

Contents

AppetizersI

Introduction11.1Fundamentals......................
1.2TheNeedforSpeed...................
1.3ImageProcessingChain................

ArchitectureComputer22.1BriefArchitectureDescriptions............
2.2DatasheetComparison.................
2.3OurChoice........................
2.4ConsequencesfortheAlgorithms...........
MemoryHierarchy...................
SIMD...........................
Parallelization......................
2.5Discussion........................

CourseMainII

Input/Output33.1ImageRepresentation.................
3.2EfficientI/O........