La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

Data-driven methods for compression and editing of spatially varying appearance [Elektronische Ressource] / vorgelegt von Gero Müller

De
170 pages
Data-Driven Methods for Compression andEditing of Spatially Varying AppearanceDissertationzurErlangung des Doktorgrades (Dr. rer. nat.)derMathematisch-Naturwissenschaftlichen Fakultätder Rheinischen Friedrich-Wilhelms-Universität Bonnvorgelegt vonDipl.-Inf. Gero Mülleraus KölnBonn, Dezember 2008Universität BonnInstitut für Informatik IIRömerstraße 164, D-53117 BonnAngefertigt mit Genehmigung der Mathematisch-NaturwissenschaftlichenFakultät der Rheinischen Friedrich-Wilhelms Universität BonnDekan: Prof. Dr. U.-G. Meißner1. Referent: Prof. Dr. Reinhard Klein2. Prof. Dr. Volker Blanz3. Referent: Prof. Dr. Jan KautzTag der Promotion: 1. September 2009Erscheinungsjahr 2009Diese Dissertation ist auf dem Hochschulschriftenserver der ULB Bonnhttp://hss.ulb.uni-bonn.de/diss_onlineelektronisch publiziert.CONTENTSZusammenfassung vAbstract viiAcknowledgements viii1 Introduction 11.1 The Complexity of Surface Appearance . . . . . . . . . . . . . . 21.2 Image-based Rendering and the BTF . . . . . . . . . . . . . . . . 41.3 Main Contributions and Thesis Structure . . . . . . . . . . . . . . 52 Preliminaries of Visual Appearance 92.1 Basic Radiometry . . . . . . . . . . . . . . . . . . . . . . . . . . 102.1.1 Radiometric Quantities . . . . . . . . . . . . . . . . . . . 102.1.2 Photometric . . . . . . . . . . . . . . . . . . . 122.2 The Rendering Equation . . . . . . . . . . . . . . . . . . . . . . 122.3 Material Classification for Computer Graphics . .
Voir plus Voir moins

envData-Dri

Editing

of

Methods

orf

essionCompr

and

ppearanceAaryingVSpatially

Dissertation

zurErlangungdesDoktorgrades(Dr.rer.nat.)
derakultätFMathematisch-NaturwissenschaftlichenderRheinischenFriedrich-Wilhelms-UniversitätBonn

vorgelegtvon

MülleroGer.Dipl.-Inf

Kölnaus

2008DezemberBonn,

BonnersitätvUniIIInformatikfürInstitutBonnD-53117164,Römerstraße

AngefertigtderakultätF

Dekan:

Mathematisch-NaturwissenschaftlichenderGenehmigungmitRheinischenFriedrich-WilhelmsUniversitätBonn

Prof.

.Dr

U.-G.

Meißner

1.Referent:Prof.Dr.ReinhardKlein
2.Referent:Prof.Dr.VolkerBlanz
3.Referent:Prof.Dr.JanKautz

TagderPromotion:1.September2009
2009ErscheinungsjahrDieseDissertationistaufdemHochschulschriftenserver

der

http://hss.ulb.uni-bonn.de/diss_onlinepubliziert.elektronisch

ULB

Bonn

Zusammenfassung

Abstract

wledgementsAckno

CONTENTS

v

vii

viii

1oductionIntr11.1TheComplexityofSurfaceAppearance..............2
1.2Image-basedRenderingandtheBTF................4
1.3MainContributionsandThesisStructure..............5

2PreliminariesofVisualAppearance9
2.1BasicRadiometry..........................10
2.1.1RadiometricQuantities...................10
2.1.2PhotometricQuantities...................12
2.2TheRenderingEquation......................12
2.3MaterialClassificationforComputerGraphics...........13
2.3.1HierarchyofDetail.....................14
2.3.2HomogenousMaterials...................15
2.3.3HeterogenousMaterials..................15
2.4ClassicalReectanceModeling...................16
2.4.1ReectanceonIdealizedSurfacePatches.........17
2.4.2BRDFModels.......................18
2.4.3BeyondBRDF-Modeling..................19
2.5Image-BasedRenderingandtheBTF................21
2.5.1LightFieldsandthePlenopticFunction..........22
2.5.2TheReectanceField...................22
2.5.3BidirectionalTextureFunction...............24
2.6Image-BasedAppearanceAcquisition...............25
2.6.1LightTransportMatrix...................25
2.6.2CapturingtheLightTransportMatrix...........26
2.6.3BTFAcquisition......................27

i

I

3

4

5

6

essionCompr

CONTENTS

31

33oundBackgr3.1MatrixFactorization........................35
3.1.1SingularValueDecomposition...............35
3.1.2Block-WiseFactorization..................38
3.1.3Two-passFactorization...................42
3.1.4TensorFactorization....................44
3.1.5AlternativeMethods....................47
3.2Summary..............................48

FactorizingtheBTFTransportMatrix51
4.1MatrixDataArrangement......................51
4.2TensorDataArrangement......................53
4.3DealingwithColor.........................54
4.4EmpiricalComparison.......................55
4.4.1StandardSVD.......................57
4.4.2Block-wiseSVD......................60
4.4.3TensorFactorization....................66
4.5Summary..............................70

Data-DrivenLocalCoordinateSystems73
5.1Uniformlocalframealignment...................76
5.1.1Sphericalcorrelation....................78
5.1.2Generalizationto4D....................79
5.1.3PuttingitTogether.....................81
5.2Non-uniformlocalframealignment................82
5.3ExperimentsandResults......................82
5.3.1SyntheticData.......................83
5.3.2MeasuredBTFs.......................83
5.3.3MeasuredFar-FieldSurfaceReectanceField.......86
5.4Summary..............................87

RelatedandConcurrentWork89
6.1FittingParametricModels.....................89
6.2FixedBasisProjection.......................90
6.3HybridModels...........................91
6.4MRF-Modeling...........................92
6.5PhotometricStereoandAlignmentofReectance.........93

ii

CONTENTS

95EditingII97oundBackgr77.1TextureTransferandImageAnalogies...............99
103BTF-Analogies88.1Multi-ChannelImageAnalogies..................103
8.2FeaturesforBTFanalogies.....................107
8.2.1SingleRGB/Luminanceimages..............107
8.2.2Reconstructedheight-map.................107
8.3ExperimentsandResults......................110
8.3.1Painting...........................110
8.3.2Warping...........................111
8.3.3Transfer...........................111
9Analogy-DrivenBTFInterpolation117
9.1InterpolatingMultipleBTFs....................117
9.2ProceduralLeatherMeso-Geometry................119
9.2.1ProceduralVoronoiCrackPatterns.............120
9.2.2EfficientCrackPatternComputation............121
9.2.3MorphingProceduralCrackPatterns............121
9.2.4FittingCrackPatternstoMeso-Geometry.........123
9.3ExperimentsandResults......................123
10RelatedandConcurrentWork129
10.1AppearanceModelingandEditing.................129
10.2Texturesynthesisandtransfer....................130

133eClosurIII135Conclusions1111.1Summary..............................135
11.2FutureWork.............................137
141yBibliograph155cesSourData157PublicationsofList

iii

vi

C

O

N

T

E

N

T

S

ZUSAMMENFASSUNG

DasrekteWoptischeahrnehmungReexionsvunderhaltenEinschätzungvoneinerMaterialienSzeneundvonOberächengroßeristfürBedeutung.diekorDer-
spezifischeGlanzunddieTextureinerOberächegebenbeispielsweiseAuskunft
imdarüberFalle,obeineseinTextilsMaterialausglatteineroderBaumwporös,oll-weichoderoderSynthetikfhartist,aseroderbesteht.sogar,Inobderes
rechtComputergrafikstiefmütterlichwurdenbehandelt.dieseAspekteDieskanneinermanSzenebiseinerseitsvordaraufwenigenJahrenzurückführen,noch
dasslismusmansichmöglicherweisederBedeutungnochnichtvonMatausreichenderialienbefürwusstdiewWar.ahrnehmungAndererseitsvonistRea-das
kleinenModellierenundvkonomplexenMaterialienStrukturenaufgrundsowiederderenbeteiligtennicht-trimikro-vialenundEinussmesoskaufopischdas
Reexionsverhaltenausgesprochenschwierig.Diesgiltinsbesondere,wennnur
klassischechenmodellezurVModellierungstechnikerfügungstehen,enwiederenPparametrischearameterhäufigReexions-unintuitiundvzuOberä-bedie-
nensindunddieunterUmständengarnichtinderLagesind,dasgewünschte
erzeugen.zuerhaltenVAnstelleAndiesemeinesPunktparametrischensetzennundieModellssowerdengenanntendaten-ggemesseneetriebenenDatendesVerfzuahrenvisuali-an:
sierendenGeometriedatenObjektsodervmitteerwendet.lseinesBeispielehiMotion-CaptureerfürsindperSystemsLaserscannergewonneneakquirierteBewe-
fahrengungsdaten.schonInseitderFvielenormvJahrenonfürdiefotografierteneffektiTveexturenRepräsentationsindkdaten-getriebeneomplexerVMate-er-
Einsatz.imrialoberächendieInBi-dirdieserektionaleArbeitTesollesxturfunktionnunum,einekurzBTFerweiterte.ImDefinitionUnterschiedvonzuTegexturenwöhnlichengehen:
TeBTFxturen,ausdievielenmeistBildern,nurdiedurchuntereinveinzigeserschiedenenBildBeleucrepräsentierthtungenwerden,undunterbestehtverdie-
schiedenenBlickwinkelnaufgenommmenwurden.Somitrepräsentierensiedas
AusseheneinesMaterialsunterderVariationvonBeleuchtungs-undBetrachter-
großerichtung.MengeLeidervonfindetBildern,dieBTFwelcheininderderRePraxisgelbishererforderlichkaumVist,umerwendung,eindaMaterialdie
mitausreichenderGenauigkeiterfassenzukönnen,schwerzuverarbeitenist.

v

ZUSAMMENFASSUNG

IndervorliegendenArbeitwerdennunVerfahrenvorgestellt,welchedieprak-
tischeAnwendbarkeitderBTFdeutlichverbessernsollen,indemsieerstens,die
zutierenderspeicherndeBTFDatenmeermöglichen.gedeutlichDementsprechendreduzieren,undbestehtzweitens,diesedasArbeitefimfizientewesentli-Edi-
eilen:TzweiauschenDerersteTeilstelltTechnikenvor,welcheinderLagesind,dieDatenmenge
unterOriginalgrößeBeibehaltungzuderreduzieren.visuellenHierbeiQualitätwirdefimfektivbesonderenaufwenigerdaraufalsWeinertgeleProzentgt,dassder
sicheinzelneDatenwertemöglichsteffizientwiederausderkomprimiertenDar-
stellungsystemenrekunerlässlichonstruierenist.lassen,DiewasGrundideefürdiedervinteraktiorvegestelltenDarstellungAlgorithmeninRendering-besteht
darin,mathematischeVerfahrenausdemBereichderFaktorisierungvonMatrizen
aufdiegemessenenDatenderBTFzuübertragen.EinweitererwesentlicherBei-
vtragondieseslokalenTKeilsderoordinatensystemenDissertationistreineinaufefBasisfizienterderAlgorithmusgemessenenzurDaten.DerBerechnungAl-
gorithmuskommtimGegensatzzufrüherenArbeitenzudiesemThemaohnedie
aus.ReektionsmodellsspezifischeneinesAnnahmeImzweitenTeilgehtesdannumAlgorithmen,diedieVeränderungderStruk-
turunddesReexionsverhaltenseinerBTFermöglichen,ohnejedesdervielen
durchtausenddieBilderFähigkeiteinzelnaus,füreinfsichacheeditierenzuEditieroperationen,müssen.dieUnsereaufTeinechnikeinzelneszeichnetBildsichan-
gewendetwurden,konsistentaufdengesamtenDatensatzübertragenzukönnen.
ZudiesemZweckgreiftunsereMethodeaufTechnikenausdemBereichderTex-
EintursyntheseweitererundAspektdesTeunseresxturtransfersVerfahrenszurückistdieundvsinnvolleerallgemeinertInterpolationdiesevaufonBTFs.BTFs
basierendaufverallgemeinertemTexturtransfer.DiesermöglichtdasEditierender
ReexionseigenschaftenvonBTFsaufeinevollständigdaten-getriebeneArtund
eise.W

vi

ABSTRACT

forThetheopticalperceptionreectanceofabehascene.viorTheofspecificmaterialsglossandandsurftheacesteisxtureofofgreatasurfaceimportancegive
vporous,aluablesofthintsoronfirmorpropertieseven,inofthethecasematerialofaitteisxtile,madeifitof;islikmadeeifitfromissmoothcotton-oror
beensyntheticslightlyfibers.overlDuringookedtheandearlymaterialsyearsofwereComputermodeledGraphicsbasedonthesequiteaspectssimplehavas-e
tothesumptionsfactthataboutatthatreectancetimetheandtexturcommunityehadappearance.notrealizedMaybethethiscanimportancebeofappointedsur-
faceparticularlyappearancedifficultinitstofullmodel:extent.theinvAnotherolvedmicro-reasonandmightbemesoscopicthatmaterialsstructuresarehavjuste
amodelsnon-trithatvialhaveinuencebeenonusedtheforreectathencebeharepresentationviorandofsurfappearance.aceappearanceThestandardduring
thethisfirstcompletwoxityindecadesanefoffectivecomputerandintuitigraphicsvewaywere.clearlynotsufficienttomodel
Atparametricthismodelpointthetheideaso-calledistobasedata-driventhescenemethodsrepresentationstepin:oninsteadmeasurementsofusingofa
theimageobjectgeneratonewionantsaretolaservisualize.-scannedCommongeometryedataxamplesorforanimationthisdatdata,a-drivenacquiredwaybyof
drivenmotion-capturemethodsaresystems.alreadyIntermscommonofspatiallypracticevinthearyingformmaterialoftexturesappearancewhichdata-are
usuallyspecialphotographsofamaterial.
tures:InthethisthesisBi-directionalwewillTedealxturewithanFunctionextended(BTF).Indefinitioncontrastoftoclassicalordinaryteimagextures,tex-
whichusuallyconsistonlyofasingleimage,asampledBTFcomprisesthousands
ofentvieimageswpoints.whichhaThisvewbeenaythecapturedBTFunderrepresentsvariousthelightappearancesituationsofaandmaterialfromdifunderfer-
varyingview-andlightdirectionwhichexplainsitsdefiningtermbi-directional.
DueaccuractoythethelargeBTFisnumberrarelyofusedimagesinrequiredtodaystopracticalcaptureapplthisbehaications.viorwithThissufdisserta-ficient
tionmethodsaimsforatefimprofectivvingeBTFthedatapracticalreductionapplicabilityandediting.ofBTFsbyConsequentlyintroducing,thenothesisvel
parts:otwofconsists

vii

ABSTRACT

sizeofThethefirstdatapartthatneedsintroducestobeandstoredcomparesondiskdotechniqueswntolessforthanreducingonethepercenteffectiofvthee
ficientoriginalsizereconstructionwhilefrompreservingthethecompressedvisualquality.representationSpecialwhichemphasisisislaidindispensableonef-
fortechniquesinteractiisvetodisplaytransferinalgorithmsrenderingknownapplications.fromtheThefieldmainofmatrixideaofftheactorizationpresentedto
BTFdata.Anothersubstantialcontributionofthisworkisanefficientalgorithm
fordatathealone.Incomputationcontrastoftolocalpreviouscoordinatemethodssystemsitdoesfromnottherarelywonmeasuredassumptionsreectanceabout
aInspecificthesecondreectionpartmodel.wewillpresentalgorithmswhichenableeditingofthespa-
oftialimagesstructureindiandviduallyreectance.OurofthetechniqueBTFiswithoutcharacterizedtheneedbytothetouchconsistentthethousandsandin-
wholeteractivedata.transferForthisofsimplepurpose,editingwegeneralizeoperationstechniquesperformedknoonawnsinglefromteimagexturetosyn-the
thesisandtransfertoBTFs.Furthermore,weintroducemeaningfulinterpolation
loofwsdiftoferentintuitivBTFselyeditbasedtheironourreectancegeneralizedinacompletelyappearancedata-dritransfervenwaytechnique..Ital-

viii

ACKNOWLEDGEMENTS

Thefamousmetaphoroftheresearcherstandingontheshouldersofgiantsoften
cametomymindwhilewritingthisthesis.
ThefirstgiantIwouldliketothankismysupervisorProf.Dr.ReinhardKlein
berwhomanalloywedfruitfulmetosetdiscussionsmyfeetbothonhisofusshoulstandingdersanyintime.frontIofwillthefdeeplyamousremem-white
blackboardresultinginmanyofthefindingspresentedinthisthesis.Withouthim
recognizingthepotentialofimage-basedmaterialrepresentationsthisworkwould
haveneverbeenpossible.
veryAsgratefulrepresentatitoProf.vesDr.forVtheolkercomBlanzputerandgraphicsProf.Dr.JanresearchKautzwhocommunitykindlyIamagreedalso
toserveasexternalreviewers.
DuringthelastyearsIhaverealizedhowmuchluckitistoworkinanenviron-
andmentIhawithvesotoemanxpressywmyonderfulbiggestcolleaguesthankstoasallinofthethem.BonnInComputerparticular,IGraphicswouldgrouplike
tomentionGerhardBendels,DirkKoch,JanMeseth,MartinRump,RalfSarlette
andMirkoSattlerwithwhomIhadthepleasuretopublishandco-authorpapers
andalsoPavelBorodin,DominikNovotni,FerencKahlesz,RuwenSchnabeland
MarkusSchlattmannwhohavebeenmostpleasantofficematesovertheyears.I
wouldmeasurementespeciallydevicesliketointhethankworld.RalfRalfSarlettelikewhoGerhard,undoubtedlyJan,bMarcin,uildstheFecu,bestMirkBTFo,
Michael,Ákos,PatrickandRolandisalsooneoftheearlymembersofthegroup
(thefirstgeneration)andIamquitegratefultothemforshapingnotonlymy
scientificbutalsomypersonallifeinmanywaysIdidnotevendreamofinthe
ginning.beIwillnotforgettomentiontheEuropeanUnion,theDeutscheForschungsge-
meinschaftandtheUniversityofBonnwhichwerethefinancinginstitutionsof
myworkovertheyears.
AndlastbutbyfarnotleastIwanttothankmyfamilyfortheirloveand
endlesssupport-thisworkisdedicatedtoYou.

ix

x

A

CKNOWLEDGEMENTS

CHAPTER1

INTRODUCTION

Ingrowingrecentyears,interestbothdata-drivfromenthetechniquescomputerfordigitalgraphicscontentresearchcreationcommunityhaveandattractedin
practicalapplications.Thesimplebutpowerfulideabehindtheconceptofdata-
drivenrepresentationsistogeneratenewcontentbyintelligentlycombiningele-
mentsalreadyavailableinadatabase.
gameSuppose,orafordigitalexample,movie.adigitalClassicalcharactermodelingneedstechniquestobewcreatedouldforrequireacomputermodeling
1thepatches.physicalDependingshapeofonthethedetailcharacterrequestedusing,e.g.bythesubdivisionapplication,surfthisacesmayorevNURBSenre-
alsoquirehashatovingbetomodelanimated,evalleryofsinglethesewrinklemodeledandhairgeometriconthedetailsskin.haIfvethetobecharacteraccu-
belieratelyvmoablevedanimationaccordingofthetoftheacialpheysicalxpressions.andbiologicallawsinordertocreatea
Itiseasytoimaginethat,evenwiththequitepowerful3Dmodelingandan-
imationsoftwareavailabletoday,suchanexercisewouldrequireconsiderable
artisticskillsandexperience,nottospeakoftheenormousamountoftimeneces-
saryently:.theTherefore,physicalinshapecurrentofthepractice,characterthisistaskisscannedoftenusingaaccomplishedlaserscannerrather.difSmallfer-
geometricdetaillikewrinklesandhairsarecapturedinahigh-resolutionphoto-
tograph.recordSubtlethemofvacialementseofxpressionsreectivareepatchesrecreatedgluedbytousinganaactorsmotionface.capturesystem
Actually,thestrikingvisualqualityandphoto-realismoftodayshigh-end
computergraphicswouldnotbepossiblewithoutthesekindsofdata-driventech-
niques.Inotherwords,thesemethodsprovidesolutionsforthecomplexityand
productivityproblemofdigitalcontentcreation.Thistrendcanbeobservednot
onlyinthefieldofcomputergraphics,butalsoinothercomputersciencedisci-
plines.recordedThesamplesbestofhumanrealspeechhumanspeech,synthesizers,notonforacoinstance,mpletearemodelmainlyofthebasedvocalon
tract.1B-SplineRationalNon-Uniform

1

(a)

CHAPTER1.INTRODUCTION

(b)

(d)(c)Figure1.1:Somematerialswithcomplexsurfacestructuresatmesoscopicscale
(wovenandknittedthreadstructures(a)+(b),scratchesandindentations(c),metal-
licakesincarpaint(d))

Itmaynotbejustifiedyettospeakofashiftofparadigminmodelingof3D
contentbutitisnowcommonlyacceptedthatcurrentandupcomingmodelsof
fromrealityrealitywill.oneAswaayresult,orthetheotherrangebeofbasedrequiredondatabasesmathematicaloftoolsmeasurementsandalgorithmscaptured
increases.Insteadofclassicalparametricandgenerativemodelswhichtrytorep-
resentrealityusingasetofparametersandmathematicalinstructionsbasedon
phstatisticalysicaldataassumptionsanalysisaboutandthewmachineorldthelearningfocusnowhichwgearsaretoablewardstoextractmethodsandfromin-
terpretperceptuallyimportantpropertiesfromahugedatacloudandmakethem
availableThisforthesisefoffectifersvesolutions,applicationinmathematicalrenderingtoolssystems.andalgorithmsfortheefficient
applicationofdata-driventechniquesinthefieldofspatiallyvaryingsurfaceap-
pearance,which,inouropinion,isofparamountimportanceforthecreationof
images.syntheticablevbelie

1.1TheComplexityofSurfaceAppearance

Whenparticularlyitcomesevident.tosurfForacegoodappearancereasonthethewvisualayofhocomplewaxitysurfofaceourreectsrealwlightorldisis

2

1.1.THECOMPLEXITYOFSURFACEAPPEARANCE

stillsurroundedbyakindofmagic.Usually,thosestructureswhichdetermine
theappearanceofmaterialslikemetal,plasticorhumanskinarenotvisiblewith
thenakedeyebecausetheinterestinginteractionhappensatmicroscopiclevel.If
truthbetold,theonlyscatteringphenomenathatcanbeconsideredtobefullyun-
derstoodaremirrorreectiononperfectlyatsurfaces,transmissiverefractionat
perfectrefractorsandidealdiffusereectiononperfectlydiffusereectors.Real
surfacescontainirregularitieswhichareusuallymodeledonlystatistically"[...],
insteadofattemptingtodescribeanddealwithitssurfacecontoursinmicroscopic
p.5].[NO77,detail."Furthermore,surfaceappearanceisheavilyscaledependent:"Forexample,in
examiningthereectanceofahighlyirregularsurfacecontainingdeepcavities,
[...]itmaybepossibletoconsiderthereectanceofdifferentportionsofthe
wallsofsinglecavities(whicharethenregardedasmacroscopicirregularities).
Butwhenstudyingthepossibleeffectsofsimilarsurfaceswhichmayexiston
themoon,[...]thesearenecessarilytreatedasmicroscopicirregularities"[Nic65,
p.3].Inclassicalcomputergraphicsthereisaclear
distinctionbetweenthementionedmacro-andmi-
croscopicscales:Atmacro-scaleshapeisexplic-
itlymodeledusingpolygonsorparametricsur-
faceswhileatmicro-scalethegeometryismod-
eledstatisticallyusingparametricmodelsofre-
ectance.Aninterestingaspectisthereforethe
transitionbetweenthesescales,i.e.whereshould
wedrawthelinebetweenexplicitandstatistical
modeling?Presently,itiscommonconsentincomputer
graphicsthatsimpleblendingisnotanappropri-
atesolutionbecauseitwouldrequiretheexplicit
modelingofintricategeometricstructureswhich
overburdensrenderingsystemsandcausesseri-
ousaliasingproblems.Therefore,itisconvenient
tointroduceanotherscalebetweenthemacro-andFigure1.2:Macro-,meso-,
micro-scaleswhichdealswiththosestructureswhichandmicro-scaleinscene
aretoobigforstatisticalmodeling(becausetheymodeling.From[WAT92].
arestillvisible)andtoosmallforexplicitgeomet-
ricmodeling(becausethiswouldbetooexpensive).AsillustratedinFigure1.2
thisspecificscalebetweenmacro-andmicroscopicstructuresisthemesoscopic
orjustmeso-scale.Figure1.1showsafewmaterialswhichexhibitcomplexstruc-
turesatthismeso-scale.Itisnotverydifficulttoimaginethatsimulatingthe
appearanceofsuchmaterialsusingtheclassicmacro-andmicro-scalemodel-

3

CHAPTER1.INTRODUCTION

ingparadigmsrequiresseriouseffortsandthatdata-driventechniquescouldbeof
aluevgreathere.

1.2Image-basedRenderingandtheBTF

toSinceimprotheveearltheyberealismginningsofofcomputercomputergeneratedgraphicsimagestexturebyaddingmappingdetailhastobeensurfacesused
[BN76].Looselyspeaking,texturemappingallowstoassigna2Dimagetoasurface
bein3D.wrappedForearoundxample,theusing3Dtegeometryxturemappingmodelofanaclothimagetoofaddatesurfxtileacematerialdetailslikcane
colorpatternsandknitstructureswithoutmodelingthemexplicitly.Thissimple
becauseapproachtextureshelpedacanlotbetopaintedincreainse2Dproductiusingvitypaintofsoftwcomputerareor,evengeneratedbetter,imageryeasily
capturedfromtherealworldusingadigitalcamera.
Thislastpointdeservesspecialattention.Theprincipleofusingimagesin-
steadofgeometricmodelsforscenedescriptionandrenderingisknownasimage-
basedsamplingrandendering.Itreconstructionreplacestheprocess.traditionalTheideaismodelingtoandrepresenttherenderingappearaprocessnceofbyana
byobjectthenotdensebyitsarrayofactualemanatingmacro-,raysofmicro-geometriclightthatandcanbephotometricthoughtofproperties"filling"btheut
spacearoundtheobject.Thisarrayoflightraysisknownastheplenopticfunc-
evtionery[AB91]possibleandvieitiswpoint.easytoThus,seetakingthatitimagescapturesofantheobjectappearanceusingaofancameraobjectcanforbe
consideredassamplingtheplenopticfunction,andreconstructingthecontinuous
Inthisplenopticsense,functiontraditionalfromatexturediscretesetmappingofwhichsamplesusescanbeonlyainterpretedsinglecolorasvaluerendering.per
texel2,andwasintroducedalreadyyearsbeforethetermimage-basedrendering
wasmaterialcoined,fromcanabesingleinterpretedimage.asthereconstructionoftheplenopticfunctionofa
Withoutgoingtoomuchintothedetailsofsamplingtheory,itisobviousthata
Infsingleact,aimagesingledoesimagenotissufableficetotocaprepresentturetheonlyidealplenopticdiffusefunctionandatofsurfmostacesmaterials.which
explainsthetypicalcardboard-likelookofcomputergeneratedimageswhichuse
xtures.tesimpleonlyGenerally,theappearanceofsurfacepointschangesifviewedfromdifferent
pointsdirections:occurs,etc.highlightsmoTherefore,ve,ancoloreandxtendedglosstexturechange,descriptionocclusionbywhichotherconsistssurfaceof
2texel=shortfortextureelement

4

1.3.MAINCONTRIBUTIONSANDTHESISSTRUCTURE

Figure1.3:Comparingsimpletexturemapping(left)andBTF-rendering(right).

imagesliteraturefromthisdifdescriptionferentvieisknowpointswnisastheneededsurfacetolightreconstructfieldthese[MRP98].effects.Inthe
Reconstructingthesurfacelightfieldofanobjectfromimagesopenedup
athenewdeintroductiongreeofoferealismxtendedbutonlyimage-basedforcompletelyrepresentationsstaticscenes.whichcanThisnotmotionlyvatedbe
Fvieieldwed[DHTfrom+00],arbitraryforeviexample,wpointsbrepresentsutwhichthecanplenopticberelit,functiontoo.forThevaryingReectanceillu-
minationreconstructed(conditions.∼rendered)Duetofromthealinearsamplednatureofreectancelightfieldtransportbynelinearlywimagescombiningcanbe
differentlylitsamples–aprocesscalledimage-basedrelighting.
materialTextures,arecalledwhichBidircanbeectionalrelitTandexturwhicheFunctionsreconstruct(BTF).thesurfInitsacelightoriginalfielddefini-ofa
tion,introducedbyDanaetal.[DvGNK97]totheComputerVisioncommunity,
thetweenBTFaissimplerestrictedtexturetowhichdirectionalcontainslighting.onlyFigurealbedov1.3ariationshowsaandacomparisonBTFwhichbe-
reproducesalsothedirectionalappearancevariationofthecorduroycloth.

1.3MainContributionsandThesisStructure
inImage-basedcomparisontorenderingotheranddata-driBTFsvenarenotechniqueswaroundlikeforlaseratleastscanningawholeormotiondecadebcap-ut
turingtheyarenotquitecommoninpractice(exceptforstandardalbedotextures).
Themainreasonforthisisthehigherdimensionalityofimage-basedrepresenta-
tions.

5

CHAPTER1.INTRODUCTION

Laser-scanners,forexample,captureacloudof3Dpointsusuallylyingona
2Dmanifold.Incontrast,image-basedrepresentationshaveatleasttwospatial
dimensionsandtwotofouradditionalangulardimensionsrepresentingthevari-
ationsalongview-andlightdirections.Justtogetaglimpse:samplingeachof
thesesixdimensionswithonly100samplesalreadyresultsin1trillionmeasure-
mentsamples.Thus,theaforementionedcomplexityandproductivityproblemof
photo-realisticcomputergraphicshassomehowonlyshifted.Insteadofmodeling
geometricdetailandcomputingexpensivelighttransportwenowhavetofacethe
challenges:seriouswingfollo•Measurement-howcanappearancebecapturedefficientlyandaccurately?
•Compression-howcanimage-basedappearancebestoredcompactlywith-
fidelity?visualsacrificingout•Rendering-whatistheimpactofusingrepresentationslikeBTFsonren-
deringcostsandhowcanitbeminimized?
•Editing-howcanimage-basedmaterialsbeeditedandmanipulatedwithout
theneedtomanuallytouchallthethousandsofimages?
Whilepracticalsolutionstotheseproblemsarecrucialfortheapplicabilityof
image-basedrepresentationsliketheBTF,exhaustivelydealingwithallofthem
wouldbefarbeyondthescopeofthiswork.Inparticular,thisthesiswillnot
covertheproblemofefficientappearancemeasurement,whichisprimarilyan
engineeringproblem,neitherwillitdiscussefficientmethodsforrenderingmea-
suredmaterials.Infact,theproblemofBTFrenderingisstronglycoupledwith
thecompressionproblemsincerenderingcanonlybeasefficientasthedecom-
pressionstageofthecompressionalgorithm.
Consequently,thisthesisconsistsoftwomainparts:compression(chapters
3–6)andediting(chapters7-10).InPartIweimprovethestate-of-the-artinBTF
compressionbyintroducingthefollowingscientificandtechnicalcontributions:
•Comparisonofmatrixfactorizationtechniques–Manyexistingdata-
drivencompressiontechniquesmakeuseofmatrixfactorization.Basedon
thegeneralmodelofco-variances,matrixfactorizationallowstoremove
redundantinformationfromthedatawhilepreservingvisuallyimportant
features.Thereisanabundanceofpossibilitieshowmatrixfactorizationcan
beappliedtohigh-dimensionaldata.InChapter4wewillcomparedifferent
matrixfactorizationmethodsconcerningcompressionratio,reconstruction
errorandreconstructioncostinordertogiveconcretehintsforselectingthe
mostsuitabletechniqueforagivensituation.

6

1.3.MAINCONTRIBUTIONSANDTHESISSTRUCTURE

•Localcoordinatesystemsforimage-basedrendering–Itiswell-known
thatcompressionofimage-baseddatagenerallybenefitsfromknownge-
ometrybuttheextractionandseparationofthegeometryfromthedatais
difficult.InChapter5weintroduceaneffectivemethodwhichexploitsap-
proximategeometryinformationforcompressionwithouttheneedtosepa-
rategeometryandreection.Themostinterestingpartofouralgorithmis
anovelvariantofphotometricstereobasedontheefficientcomputationof
correlationsbyexploitingthegeneralFourier-ShifttheoremforSpherical
Harmonics.PartIIofthisthesisintroducesoneoftheveryfirstmethodsforeditingmea-
suredBTFsandcomprisesthefollowingcontributions:
•BTFAnalogies–Thesheersizeofimage-basedrepresentationsmakes
themparticularlydifficulttoedit.Methodsarerequiredwhichpropagate
simpleeditingoperationstothehigh-dimensionalrepresentation.InChap-
ter8wepresentourBTFAnalogiestechniquewhichgeneralizesthewell-
knownImageAnalogiesframework[HJO+01]toBTFs.Thealgorithmis
abletointeractivelyandconsistentlypropagateeditsappliedtoproxyim-
data.wholethetoages•MeaningfulBTFInterpolation–BasedontheBTFAnalogieswepro-
poseamethodformeaningfulinterpolationofBTFs.Byemployingalso
aproceduraltexturemodelnewBTFscanbecreatedfromadatabaseof
measurementsinameaningfulandintuitiveway(Chapter9).
Beyondthesetwomainpartsthethesiscontainsfurthermoreabackground
chapterwhichfollowsimmediatelyafterwardsandpresentsthenecessaryprelim-
inariesofthetheoryandpracticeofimage-basedmaterialrepresentationslikethe
BTF.Itincludesanintroductionintothetheoreticalfoundationsofsurfacere-
ectanceandlighttransport.ThethesisisconcludedinChapter11wherealso
possibledirectionsforfutureresearchwillbediscussed.
Asusualinthefieldofcomputergraphicsmostofthealgorithmspresentedin
thisthesishavealreadybeenpublishedatseveralinternationalcomputergraphics
conferences[MMK03,MMK04b,MBK05,MSK06,MSK07].Wealsopresented
severalofthetechniquesdiscussedhereinawell-recognizedstate-of-the-artre-
port[MMS+05]andatvarioustutorialsattheannualSiggraph[LGC+05]and
conferences.[LGM07]Eurographics

7

8

C

HAPTER1

.

I

NTRODUCTION

CHAPTER2

PRELIMINARIESOFVISUALAPPEARANCE

itThewithvisualthenakappearedeye.anceofThisanincludesobjectrefersgeometrictoevattriberythingutesthatlikecanshapebeandperceisizevedbutof
tiesalsolikematerialsoftness,attributesbrittleness,likecolorage,oretc.Thetranslucencysimulationaswellofassuchmorematerialfuzzyappearproper--
ancestructuresattribinutesvolvwithedaareusuallycomputerisquitesmaparticularlyllwhichmakchallenging,esanbecauseaccuratethephysicalgeometricsim-
ulationinfeasible.Therefore,reasonableabstractionshavetobeusedwhichcan
bemodelsbasedonwhichphcanysicsefbutficientlyabovebeallevshouldaluatedbycondensecomputers.thephysicaldetailintocompact

ThemostfundamentalabstractioninComputerGraphicsisprobablythelight
transport-orrenderingequation.Sinceitiselaboratelycoveredinmoststandard
ComputerGraphicstextbooks(e.g.[CWH93]or[PH04])wewillgiveonlyabrief
introductiontotherenderingequationandthenecessaryradiometrictermsinSec-
2.2.and2.1tions

Themainconcernofthisthesisisthevisualappearanceofmaterials.There-
fore,wewillstatemorepreciselywhatmaterialsareandhowtheyarecatego-
rizedforthepurposeofvisualizationinSection2.3.Thenwewillintroducethe
twodifferentparadigmscurrentmaterialmodelsarebasedon:atfirstphysically-
based,parametricmodelingofappearance(Section2.4)and,secondly,image-
basedmeasurementandrendering(sections2.5and2.6).

2.14).TheOurcentral(simplified)definitionderiofvationthiswaschapterinspiredisthebylightLehtinentransportsframematrixworkfor(Equationpre-
computedandcapturedlighttransport[Leh07]whichisstronglyrecommended
reading.furtherfor

9

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

RadiometryBasic2.1ComputerGraphicsisaveryyoungscientificdiscipline.Nevertheless,itstheo-
reticalfoundationsrangebackmorethan3000yearsintotheclassicdisciplineof
optics.Opticsistraditionallystudiedonthreedifferentscaleswhereeachscale
hasitsownstrengthsandweaknessesinexplainingspecificvisualphenomena.
Onthescaleofsingleatomsquantumopticsdescribestheinteractionbetween
photonsandmoleculesorevenatomswhichisusuallytoodetailedforthepurpose
ofvisualization.Waveopticsisconcernedwiththeinteractionoflightwithobjects
thesizeofwhichliesintherangeofthewavelengthoflight.Itenablestodescribe
effectssuchaspolarizationanddiffractionwhichcause,e.g.thefamiliarrainbow
patternsthatappearonacompactdisc.However,theseeffectsareusuallynot
modeledexplicitlyinComputerGraphics.
Instead,mostimagegenerationalgorithmsarebasedontheprinciplesofray
opticswhichexplainsthepropertiesoflightonamacroscopicscale.Itisassumed
thatlighttravelsinstantaneouslythroughamediumalongstraightlines.Anim-
portantconsequenceofrayopticsisthatthelightdistributionatapointxinspace
isgivenbytheraysLi(x,ωi)incidentatxfromeachdirectionωi∈Ω.Inorder
toquantifysuchalightdistributionweneedtospecifyitsphysicalunits.Inpar-
ticular,weneedtospecifytheunitsofenergycarriedbyasinglelightray.Since
inphysicslightisthoughtofaselectromagneticradiationtheunitsoflightare
usuallydescribedintermsofradiometrywhichisthescienceofthephysicalmea-
surementofelectromagneticenergy.TheimportantunitforComputerGraphics
whichquantifiestheamountofenergycarriedbyasinglerayisradiance.Itwill
bederivedinthefollowingsubsection.

QuantitiesRadiometric2.1.1ThefundamentalquantityinradiometryistheradiantenergyQexpressedin
Jtonsoule[Jwhere].oneIntuitivelyphoton,anhasamountanenerofgylightofener∙cgyandwherecorrespondsistoaPlancknumbersofconstant,pho-
λciscountingthespeedphotonsoftralightvelingandλwiththethewavspeedelengthoflightassociatedcanbewithratherthetediousphoton.(evenSincefor
computers),differentialquantitiesaremuchmoreconvenientinspecifyinglight
.gyenerTheradiantpowerΦ=dQ,alsocalledux,whichisexpressedinWatt
[W]=[Js−1],denotesthenumberdtofphotons(whichmeanstheamountofen-
ergy)owingfrom/to/throughasurfaceperunittime.
bringsPouswertodoesirrnotadiancegiveEany=dΦinformationwhichisaboutethexpresseddensityin[Wofmthe−2]lightandow.quantifiesThis
theincidentpowerperunitsurfdAacearea.Theemittedanaloguetoirradianceis
10

2.1.BASICRADIOMETRY

(b)(a)Figure2.1:(a)Geometryofthedifferentialsolidangle.Bydefinitionthesolid
anglesubtendedbyasphericalareaAisequaltoA/r2.Itfollowsdω=dA/r2=
sinθdθdφ.(b)Geometryofradiance:uxperdifferentialprojectedareadA⊥per
differentialsolidangledωinthedirectionωi.

radiositywhichisawell-knownquantityinComputerGraphicssincetheradiosity
algorithm,whichessentiallycomputestheradiosityofdiffusesurfacepatches,has
it.afternamedbeenKnowingthedensityofthephotonowatagivenpointdoesnotsufficeto
describetheappearanceofthepointwhenviewedfromaparticulardirection.
Intuitively,weneedtospecifythephotondensityperdirection.Sinceadirection
haszeroextentwealsoneedtodefinesomethinglikea"directionwithextent"
whichistheroleofthedifferentialsolidangledωillustratedin2Figures2.1.
In−1terms−2ofuxwe⊥thenhavetheradianceL(X,ωi)=dωddAΦ⊥(expressedin
[Wsrm])wheredA=dAcosθistheprojectedareaofthedifferentialsur-
faceelementdAontothehypotheticaldifferentialsurfaceperpendiculartoωi
whichsubtendsthesolidangledω(seeFigure2.1(b)).Thecosinetermstems
fromthefactthattheemittedpoweris"smeared"overalargerareawhenseen
angles.wshallofromRadianceisthefundamentalradiometricquantityinraytracingalgorithms
sinceitremainsconstantalongraysinemptyspaceandthusdescribestheenergy
"carried"byaray.Furthermore,asindicatedabove,renderingascenefroma
givenviewpointcannowbeinterpretedascomputingtheradianceincidentatthe
viewpoint.Lastbutnotleast,otherquantitieslikeirradianceandtotaluxcan
becomputedbyintegratingoverdirectionsandarearespectively.Lightsensors
suchascamerasandthehumaneyearesensitivetoradianceinthesensethattheir

11

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

PhotometryRadiometryysicsPhFluxRadiantpower[W]=[Js−1]Luminouspower(lumens)
FluxdensityIrradiance[Wm−2]Illuminance(lux)
AngularuxdensityRadiance[Wsr−1m−2]Luminance(nit)
Table2.1:Radio-andphotometricunits

responseisalwaysproportionaltotheincidentradiance.

QuantitiesPhotometric2.1.2Sincetheactualresponseofthehumaneyetolightenergyisnotequalacrossthe
visiblespectrumitisusefultoknowalsoabouttherelationsbetweenradiometry
andphotometrywhichdealswiththeperceptionoflightenergyinthehuman
brain.Historically,radiometryevolvedfromtheareaofphotometrybutsincethe
radiometrictermsaremoregeneralthanphotometrictermsandthephotometric
quantitiescanbecomputedfromradiometricquantitiesitiscommonstandardto
useradiometricquantitiesinComputerGraphics.
Theradiometricquantitiesintroducedabovecanbederivedpurelyfromthe
geometryofows(whichweomittedhere,seee.g.[CWH93,chp.2])butimpor-
tantpropertiesofradiationsuchastheinversesquarelawhavealreadybeendis-
coveredbeforethefoundingofradiometrywhilestudyinghumanvision.Theclas-
sicalunitsfromphotometrycanbederivedfromthegeneralradiometricunitsby
integratingthemagainsttheso-calledspectralluminousefficiencyfunctionV(λ)
whichquantifiesthesensitivityofthehumaneyeforagivenwavelengthλandis
definedfordaylight(photopic)andnightvision(scotopic).V(λ)isgreaterthan
zeroforwavelengthsbetween380and780nmandhasitsmaximumaround550
nmwhichisperceivedasgreen.
Table2.1showsanoverviewoftherelevantphotometricunitsandtheirradio-
counterparts.metric

EquationRenderingThe2.2Theformalframeworkofrenderingistherenderingequationasintroducedby
Kajiya[Kaj86].Itisbasedongeometricopticsandthelawofconservationof
energy.Wegivethedirectionalformulationforopaquesurfaceshere:
Lo(x,ωo)=Le(x,ωo)+fˆ(x,ωi,ωo)Li(x,ωi)cosθidωi(2.1)
+Ωi12

2.3.MATERIALCLASSIFICATIONFORCOMPUTERGRAPHICS

Accordingly,thisequationdescribestheoutgoingradianceLoatapointxonasur-
faceindirectionωoasthesumoftheemittedradianceandthereectedradiance
whichistheintegralovertheupperˆhemisphereofincomingradianceLitimesthe
spatiallyvaryingmaterialpropertiesf(whichwillbeintroducedinSection2.4)
timestheforeshorteningfactorcosθi.SincetheincomingradianceLi(x,ωi)can
beinterpretedastheoutgoingradianceatthepointseenfromxindirectionωithe
renderingequationconsistsofarecursiveandthusinfinite-dimensionalintegral.
Mathematically,equationsofthisformarecalledFredholmequationsofthesec-
ondkindwhichingeneralhavenoknownanalyticsolution.Therefore,rendering
algorithmsrelyonnumericaltechniqueslikeMonte-Carlointegration,whichis
oftenimplementedbyray-tracingalgorithms,tofindapproximatesolutionsfor
Lo(see,e.g.[PH04]foranintroduction).Pleasenote,thattherenderingequa-
tionisassociatedwithsurfacepointsxwhichhavelocalreectanceproperties
fˆ(x)whichmeansthatnon-localeffectslikeshadowsorinter-reectionshaveto
beassumescomputedopaqueaspartmaterials,ofsolvingi.e.lighttheisintegraldirectlyequation.reectedattheFurthermore,pointoftheincidence.equation
Inordertosimulatealsoobjectswithtranslucentmaterialsthedefinitionof
surfacescatteringbehaviorandthedomainofintegrationhastobeextended.In
particular,weneedtointegrateoverincomingdirectionsandsurfaceareaofthe
object:translucentLo(x,ωo)=Le(x,ωo)+S(xi,ωi;x,ωo)Li(xi,ωi)cosθidωidA(xi)(2.2)
AΩi+(xi)
Thisway,alsolightincidentatpointxi=xandscatteredtoxisintegrated.The
scatteringbehaviorofthematerialisencodedinthegeneralscatteringfunctionS.

2.3MaterialClassificationforComputerGraphics
icalMaterialobjectin.theAwsenseall,forofestuffxample,isaissubstancemadeofthatstone,goesaintocupisthemademakeupofofaporcelain,phys-
etc.rizingHumansuchstufflanguagebutithasremainsdevelopedunclearahorichwvmostocabofularytheseforcatedescrgoriesibingandtranslatecateintogo-
beformaldescribedrepresentationsmathematicallyofmaterials.isstillFanoropeninstance,question.howa"ufTherefore,fy"materialinComputershould
ematicalGraphicsmaterialsrepresentationarewhiusuallychthenclassifiedconstrainsbasedtheonthevisualcomplephenomenaxityofthattheircanmath-be
causerepresentedthebyincomingit.Forlighteisxample,onlyininteEquationgratedo2.1verthematerialsupperarealwhemisphere.aysopaqueFirstlybe-,
letusComputerspecifyGraphics.moreNotrigourouslysurprisinglywhat,thispartsisofaaquestionsceneareofscale.definedasmaterialin
13

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

2.3.1HierarchyofDetail
Everyvisualsurfacecharacteristicistheresultofaninteractionbetweenlightand
matter.Asalreadymentioned,theexplicitmodelingofallgeometricdetailsis
infeasibleandtherefore,notwithoutreason,therenderingequationseparatesbe-
tweenexplicitlymodeledgeometryontheonehandandgeometrythatisencoded
withinthe"black-box"scatteringfunctionsfˆandSontheotherhand.Thissepa-
rationcanbeunderstoodastwodifferentlevelsofdetailwhichdemanddifferent
representations.Theselevelsarenotstaticbutdependonscale,e.g.thesurface
ofthemooncanberegardedasamaterialwhenobservedfromtheearthbutit
shouldbemodeledasgeometryforavirtualastronautlandingonit.Infact,we
canimagineaninfinitehierarchyoflevelsofdetail...Di−1⊂Di⊂Di+1⊂...
startingfromintergalacticdimensionsdowntosingleatomsandsoon1.Inor-
dertodealwiththisvastcomplexityKajiya[Kaj85]suggestedtoconsiderthree
differentscalesateachparticularlevelofdetailDi(seealsoFigure1.2):
•Themacroscopicscalecontainsthegeometrywhichcanbemodeledeffec-
tivelyusingsurfacemodels(likepolygonsorpolynomialpatches).This
scaleisusuallyassociatedwiththeshapeofobjects.
•Thesurfacemapping-ormesoscopic-scalecontainsdetailswhichwould
begeometricallymodeledatlevelDi+1andareusuallyrepresentedusing
texturesandbump-ordisplacementmapswhichareparameterizedacross
model.geometricthe•Evensmallerdetailswhichcouldnotberesolvedbythedisplaydeviceare
fromthemicroscopicscale.Representingdetailsfromthisscaleusingsur-
facemodelsormapswouldresultinexcessivealiasing.Therefore,thein-
uenceofthesedetailsonappearanceshouldbeaccumulatedintoreection
models,i.e.intothefunctionsfˆandSfromequations(2.1)and(2.2).
Themeso-andmicroscopicscalesareusuallyassociatedwiththematerialan
objectismadeof,i.e.withstuff.Thegeometrypresentatthesescalesgivesobjects
theircharacteristiclook.Forexample,theuniqueappearanceofacorduroycloth
isdefinedbytheweavingpatterns(meso-scale)andthereectancepropertiesof
individualthreadsandgroupsofthreads(micro-scale).
Thishierarchyofdetailsuggestsafirstfundamentalclassificationofmate-
rials:Homogenousmaterialswhicharesolelydefinedbytheirmicro-structure,
or,equivalently,bytheirdirectionalappearanceexpressedbythechangeinap-
pearancewhentheviewingpositionorthelightingchanges,andheterogenous
1Animpressivemovieillustratingthisinfinitehierarchyofdetailcanbefoundathttp://
www.powersof10.com

14

2.3.MATERIALCLASSIFICATIONFORCOMPUTERGRAPHICS

materialsthatareadditionallycharacterizedbyspatialvariationsonmesoscopic
scale.

MaterialsHomogenous2.3.2Homogenousmaterialscanbefurtherclassifiedbasedontheiropacity.
Opaquematerialsmainlyreectlightwhichmeansthatthein-scatteredfraction
ofwhichlightcancanbebeneroughlyglected.Hocharacterizedwthelightasfoisllows.reectedAverydependsroughonthe(stochastic)micro-structuremicro-
tion.structureTheotherscattersextremelightisauniformlyperfectlyinallatsurfdirectionsacewhichwhichreectsresultslightindifonlyfuseintoreec-the
surfmirroracesdirectionwhichs(aspreadthedeterminedreectedbylightthelawaroundofreaection).preferredIndirectionbetweenare(usuallyglossythe
mirrorroughnessofdirection).theThemicro-structure.widthoftFhisormanso-calledymaterialsscatteringthislobelobeiscorrelatesisotropicwithwhichthe
surfmeansacethatnormal.theOnmaterialthedoesopposite,notifchangetheitsmicro-structureappearancewhenhasarotatedpreferredaroundalign-the
mentdirection,e.g.ismadeoforientedfibersorgrooves,thereectionbecomes
anisotropicbecausethenitdependsonthe(projected)anglebetweenthelight
beamandthealignmentdirectionofthematerial.
Translucentmaterialsshowconsiderablelightscatteringwithinthematerial.
Manytranslucentmaterialscanbecharacterizedstatisticallybythedistribution
oflightabsorbingor-scatteringparticles.Opticallythickmaterialscanoftenbe
regardedasdiffusematerialsbecausethescatteringfromparticlesresemblesscat-
teringfromroughsurfaces.Iftheopticalthicknessdecreasestheresultingsub-
surfacescatteringcreatesadistinctlookknownfromuidslikemilkornatural
materialslikeleavesormarble.
Transparentmaterialsletthelightgetthroughwithoutanyscattering.Transpar-
entmaterialsarefullycharacterizedbytheirindexofrefractionwhichdetermines
howthelightrayisrefractedwhenitentersorleavesthematerial.
bemadeManyoutrealofdifmaterialsferentarelayersorcombinationsshowaoftheconsiderableaboveamountclassesofsincereectiontheymightand
dependsin-scattering.onwavOften,elengththewhichfractioncausesofthereectedsensationandofabsorbedacoloredorin-scatteredmaterial.Manlighty
heterogenousmaterialsaremadeofspatialpatternsofhomogenousmaterials.

MaterialsogenousHeter2.3.3Indust,realitetc.yHoalmostweverall,amaterialsclassificationshowofsomeheterogenousheterogeneitymaterialsduetoisdifficultimperfections,andedirt,xist-

15

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

ingonesareofteninappropriateformodelinginComputerGraphics.Therefore,
ingspatialtevxturesariationandismappedusuallytorepresentedmacro-scaleexplicitlygeometry.Ne(paintedvorertheless,captured)thereinisa2Dvus-ery
theimportantcomplexitydistinctofiontheirthatsurfcanacebeheightmadevariationbetweenonheterogenousmesoscopicscale.materials,namely
Flatometry,i.e.materialstheycancanbebefullyinterpretedcharacterizedasspatialbypatternsspatiallyofvaryinghomogenousmicro-scalematerials.ge-
Examplesareprintedpaperorfabricswithmicroscopicallysmallweavingpat-
terns.allax,Bumpyshadomaterialsws,andhavemaskingvisibleefsurffects.aceTheheightheightvvariationsariationswhichcanbecauseshading,representedparby-
map).(displacementheightfield2DaVBesidesolumetricshadowingmaterialsandcannotmaskingbeefassignedfectsathesesingledmaterialsepthvalueusuallypershosurfwacecomplepoint.x
lightshagpilescatteringornaturallikesurfinteraceslik-reectionsegrassandorfur.sub-surfacescattering.Examplesare
turalAnotherfeaturestypelikeofcolorandclassificationcontrastistogradient.considerThethekeystatisticalelementdistribhereisutionthatoftemostx-
heterogenousmaterialsaremadeofrepeatingelementsorpatternswhicharedis-
tributedinacertainway.Ifthesedistributionsareknowntheycanbeusedto
generatearbitrarylargeinstancesofthematerial.
Stocrialslikhasticesandormaterialsingrainhavewaallpapermoreorarelessofthisrandomtype.distribBasedutiononofthepatterns.alignmentMate-of
patternswecandistinguishbetweenisotropicmaterials,whichhavenopreferred
materials.anisotropicanddirection,alignmentSemi-regularmaterialsconsistofrepeatingstructureswhereeachrepetitionin-
fromtroducesgrowthslightvprocessesariationslikeinlizardcolor,skingeometryare,semi-reetc.Forgulare.xample,materialsresulting
usuallyRegularcreatedmaterialsbyarearegularmadeorofautomaticstrictlyprocessrepeatingliketextstructures.ilesmadeSuchfrommaterialssyntheticare
fibers,checkerboardorbathroomtilesetc.
onaMaterialslacqueredthatsurfacecontaincanalsobeglobaltermedpatternsgloballylikeavariantfewtexturesspatiallyv[WHZarying+08].scratches

ModelingReectanceClassical2.4tureThefortheorytheofreectionreectancefunctionsmodelingusedinprothevidestheformulationbasicofthegeometryrenderingandnomencla-Equations

16

2.4.CLASSICALREFLECTANCEMODELING

(2.1)and(2.2).Classicalreectancemodelingusuallyreferstothemicro-scale
aspectsofscenemodelingbyabstractingfromanyvisibleshapeandsurfacede-
tails.

2.4.1ReectanceonIdealizedSurfacePatches
Weassumethatabeamoflightisincidentonanidealized,locallyatsurface
patchatpointxi.Neglectingthedependencyontimeandassumingafixedwave-
lengthbandλ0forbothincomingandreectedrays(thatmeansignoringeffects
likephosphorescenceanduorescence)theappearanceofapointxoonthissur-
facepatchnowonlydependsontheincidentlightbeam(xi,ωi)andtheamount
ofenergythatisreectedfromxointhedirectionωooftheobserver.Ingeneral,
theamountofreectedenergyisproportionaltotheincomingux.Thecorre-
sponding8-dimensionalproportionalityfactoristermedbidirectionalscattering-
surfacereectancedistributionfunction](BSSRDF)[NO77]:
Sλ0(xi,ωi;xo,ωo):=dLr,λ0(xo,ωo)[sr−1m−1](2.3)
dΦi,λ0(xi,ωi)
TheBSSRDFaloneisonlyamathematicalabstraction,a"black-box".Quoting
Nicodemus,it"merelyprovidesawayofquantitativelyexpressingtheconnection
betweenreecteduxleavingxoinagivendirectionandtheuxincidentatxi
fromanothergivendirection[...]whichproducesit"[NO77,p.4].Nothing
issaidabouttheactualmechanisminvolvedoranymaterialexistinginreality
andtherepresentationiscompletelydecoupledfromtheactual(micro-)geometry.
TothisendtheBSSRDFprovidesonlyaformalizationofthebasicreection
.geometryTheBSSRDFispartofEquation(2.2)andthemaintaskofappearancemod-
elinginComputerGraphicsistofindcomputablemodelsbasedontheBSSRDF
reectiongeometrywhichdescribethereectancebehaviorofrealmaterialsand
canbeusedinrenderingsystems.Thiswillrelievethemodelingsystemfrom
explicitlyrepresentingthegeometryuptomicro-scaleandcomputingafulllight
transportsimulationforthisgeometry.Thequestionremains,howthesepractical
found.becanmodelsBSSRDFThefirststepisusuallytorestrictoneselftooneofthealreadymentioned
subclassesofmaterials.Acommonrestrictionistoassumeahomogenousand
opaquematerialbecausethensubsurfacescatteringcanbeneglectedandwehave
uniformreectionpropertiesacrossthewholesurfacepatch.Inthiscasethede-
pendencyonspatialpositioncanbedroppedforthein-andoutgoingrayandwe
arriveatthefamous4Dbidirectionalreectancedistributionfunction(BRDF):
f(ωi,ωo):=dLo(ωo)[sr−1](2.4)
dEi(ωi)
17

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

whichistheratioofdifferentialoutgoingradiancetoincomingirradiance.Note,
thatfindingthespectralappropriateindexλmodels0isforusuallythe4DomittedBRDFforisbreeasiervity.InandmancontrastydiftotheferentBSSRDFmodels,
havebeenpublishedovertheyears.

ModelsBRDF2.4.2RealBRDFsarestronglyconstrained4Dfunctions.Theyhavetofulfillphysical
constraintslikeHelmholtzreciprocityandenergyconservation.Furthermore,as
sketchedinSection2.3,theappearanceofmanyhomogenousmaterialsismore
orlessdefinedbythestatisticaldistributionoforientationsandslopesoftheun-
derlyingmicro-structureandformanymaterialsanisotropicdistributioncanbe
assumed.TheBRDFmodelsdevelopedbasedonthesekindsofobservationscan
roughlybecategorizedintoempiricalmodelsandphysically-basedmodels.The
firstgroupconsistsofmodelsthatwheredesignedtomimicthetypicalreection
behaviorofrealmaterials"payinglittleattentiontothephysicalderivationofthe
model,orthephysicalsignificanceofitsparameters"[War92,p.1].Instead,a
physicallybasedmodel"attemptstogetclosertothetruedistributionbystarting
fromphysicaltheory"[War92,p.1].
ThemostsimpleBRDFmodelisassuminganidealdiffuseorlambertianre-
ector.InthiscasetheBRDFissimplyaconstant:
f(ωi,ωo)=kπd(2.5)
with0≤kd≤1whichassuresenergyconservation.WhilealambertianBRDFis
physicallyplausible(itfulfillsthenecessaryphysicalconstraints)andareasonable
approximationformaterialslikechalkorpapernoexistingsurfaceisidealdiffuse.
Formodelingglossyreectionseveralapproacheshavebeenbeenpublished
intheliterature.Weintroduceonlymodelsrelevantforthisthesishereandrefer
theinterestedreaderformorethoroughoverviewsto[PH04,Chp.9]or[NDM05].

Cook-TorranceModelThemodelintroducedin[CT81]assumesthatthemicro-
geometryofthesurfaceconsistsofrandomlydistributedandorientedspecular
isformulaTheacets.microff(ωi,ωo)=kd+KksjFR0,j(γh)∙Dmj(θh)∙G(ωi,ωo)(2.6)
πj=0πcosθi∙cosθo
anditconsistsofanidealdiffusetermwhichaccountsforview-independentin-
ternalandmultiplescatteringandamulti-lobeglossyterm.Eachlobeconsists
ofaFresneltermF(usuallySchlicksapproximationisusedhere[Sch94])with
18

2.4.CLASSICALREFLECTANCEMODELING

parameterR0,j,themicrofacetdistributionDwhichbydefaultistheBeckman
lobesdistribKutionisequalwithto1inparameterthemjoriginal,andthepaper,shadomultiplewinglobestermGcan.beTheusednumberforofmodelingglossy
materials.layered

eLafxampleortuneforanModelempiThericalfamousmodelsincePhongitjustreectancemimicsmodeltheblurred[Pho75]isthelight-sourcetypicalre-
ectionsfunctionraised(highlights),toapowertaking.Drivplaceenbyonitssematerialsverallikedeficienciesopaquelikplasticephwithysicalaimplau-cosine
asibilitygeneralizedandvrestrictionersiontowhichisotropichasthefollomaterialswingform:Lafortuneetal.[LFTG97]designed
Kf(ωi,ωo)=ksj(Cx,jωi,xωr,x+Cy,jωi,yωr,y+Cz,jωi,zωr,z)mj(2.7)
=0jandwherem(ωarex,ωthey,ωperz)tis-lobeadirectionparameters.inTheCartesianlobescancoordinatesbedesignedandksjto,Cx,jmodel,Cyv,j,ariousCz,j
jeffectslikenon-lambertiandiffusereection(Cx=Cy=0),retro-reection
(inCx,theCy,Cgraphicsz>0)andcommunityalsobecauseanisotropicitcanreectionbee(vCxaluated=Cyef).Theficientlymodelevenisonpopularolder
graphicshardwareandcanbefittedtomeasureddata.

BRDF-ModelingondBey2.4.3ScatteringSubsurfaceForarelativelylongtimetheaccuratesimulationoftranslucentmaterialswasonly
possiblebysolvingthegeneralscatteringequationforparticipatingmediaor,as
itisusuallyreferredtoinComputerGraphics,thevolumerenderingequation:
(ω∙)L(x,ω)=−σtL(x,ω)+σsp(x,ω,ω)L(x,ω)dω+(x,ω).(2.8)
ΩThiswithinistheanintemediumgro-difalongferentialdirectionequationωdueandtoitabsorbtiondescribestheanddifferenceout-scatteringin(giradianceven
byandethextinctionphasecoeffunctionficientp)σtand),emissionin-scattering(quantified(determinedbythebysourcescatteringtermcoef).ficientSimilarσlys
tothestandardrenderingequation(2.1)thisequationcanalsobesolvedusing
quiteeMonte-Carloxpensiveintechniquesthegenerallikecase.ray-marchingbutitiseasytoimaginethatthisis

19

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

Therefore,renderingoftranslucentmaterialsbecamepracticalforthefirst
als.timeThewithythewerebasedintroductiononofassumingtheafirsthomogenousparametricandmodelshighlyforscatteringtranslucentmaterial.materi-
Inthiscasetheoutgoinglightdistributionbecomesisotropic,i.e.onlydepends
onthedistance|xi−xo|,andcanbecomputedbysimulating[Sta95]ormod-
eling[JMLH01]adiffusionprocess.TheBSSRDFmodelforhighlyscattering
materialsasintroducedin[JMLH01]readsasfollows:
Sd(xi,ωi,xo,ωo)=1Ft(xi,ωi)Rd(|xi−xo|)Ft(xo,ωo)(2.9)
πusingwhereaRdifdisfusionthedipoleradialdiffusedependingsubsurfontheaceabsorbtionscatteringandfunctionscatteringwhichcoefisficientsmodeledof
bythelowmaterialorder(seescattering[JMLH01]eventsforaredetails).usuallyMaterialsimulatedswhosedirectlyappearanceandfindingisefdominatedficient
analyticalmodelsforthiscaseisstillanopenresearchproblem.

ariationVSpatialAsmentionedabove,realmaterialsarehardlyperfectlyhomogenous.Ifthema-
terialisheterogenousbutopaquethensub-surfacescatteringcanbeneglectedand
wehaveaspatiallyvaryingBRDF(SVBRDF)(wearestillassumingaatsurface
patch):fˆ(x,ωi,ωo):=dLo(x,ωo)[sr−1](2.10)
dEi(x,ωi)
TheSVBRDFrepresentsthespatiallyvaryingreectanceintherenderingequa-
tion(2.1)andisusuallyrepresentedbydiscrete2Dcoefficientmaps(textures)
whichspatiallymodulatetheparametersofBRDFmodels.Thesetexturemaps
canbepainted,procedurallygenerated,synthesizedfromexamplesormeasured
fromrealobjects(seeSection2.5).

DetailsSurfaceMesoscopicAllmodelspresentedsofaronlyrepresenttheappearanceresultingfrom(het-
erogenous)micro-scalegeometry.Inordertoavoidtheexplicitgeometricmodel-
ingofmesoscopicsurfacedetailsnormal-anddisplacementmappinghavebeen
developed(see[SKU08]foranextensiveoverview).
Normalmapssimulatetheshadingpatternsresultingfrommesoscopicgeom-
etry[Bli78].Theideaistocomputetheshading(evaluationoftheBRDF)using
thenormalvectorsfromthemesoscopicgeometryinsteadofthemacro-scalesur-
facenormalvectors.Sincenorealgeometryiscreatedtheydonotreproduce

20

2.5.IMAGE-BASEDRENDERINGANDTHEBTF

3Deffectslikeparallax,shadowingandmaskingandasaresultnormalmapped
surfacescanappearsyntheticallyat.
Displacementmapsintheiroriginalform[Coo84]generaterealgeometryby
displacingmeshverticesinthedirectionoftheirnormalvectorwhichnaturally
reproducescorrectparallaxandocclusion.Novelpixel-basedmethodseitherper-
formdisplacementssomesort(e.g.of[WTLray-tracing+04])onwhichtheGPUare(e.g.accessed[POJ05])duringorstorerenderinginpre-computedorderto
displacethetextureaccess.Thelatterapproachcanalsobeusedtorendernon-
.meso-geometryheightfieldrenderingBothofmappingmesoscopicmethodssurfproacevidedetailsefandficientoftenmethodssupportforeftheficientrepresentationself-shadowingand
buttheydonotsolvetheproblemofefficientsimulationofcomplexhigher-order
materials.theseonlight-transport

2.5Image-BasedRenderingandtheBTF

Assketchedintheprevioussection,ComputerGraphicspossessesarichbouquet
ofmodelsandrepresentationsofmaterialappearance.Basedonthesemodels
andglobalilluminationalgorithmssyntheticimageswithphoto-realisticmaterial
appearancecanbecreatedwithacomputer.However,practicallythereisstilla
longwaytogountilthefirstconvincingrenderingwhichreproducesthefavorite
skirt-fabricorthebelovedleatherwingbackchairwillyieldasatisfyingresult.As
PaulDebevecputitintheintroductionofthenowclassicalSiggraphcourseon
image-basedmodelingandrendering[DG98]:"modelingishard,andrendering
".slowisTheserestrictionsofgeometrybasedrenderingdrovethedevelopmentofimage-
basedrenderingandmodelingtechniqueswhichaimatcapturinggeometricde-
tailandappearancefromphotographs.Whiletheterm"image-basedrendering"
wascoinedasrecentlyasinthe1990s,renderingtechniquesbasedonimages
liketexture-mapping[BN76]whereintroducedalreadyinthepioneeringyearsof
realisticrendering.Theseimage-basedtechniquesshouldnotbeseenincompe-
titiontorigorousmeasurementofreectancewhichremainstheareaofexpertise
ofphysicists(e.g.[PB96])buttheyoffersolutionsfortheefficientgenerationof
appearance.photo-realisticwithimagesThetheoreticalframeworkofimage-basedrenderingandrelightingisthere-
ectancefieldwhichisbasedontheplenopticfunction.

21

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

2.5.1LightFieldsandthePlenopticFunction
Photo-realisticimagegenerationcanbeinterpretedascomputingasetoflight
rayswhichcreatethesensationofarealisticsceneintheobserverseye.Thisset
oflightrayswillbeasubsetofofalllightraysinthesceneforafixedmomentin
time.Alllightraysandtheirassociatedradiancesarerepresentedbytheplenop-
ticfunctionP(X,ω)[AB91]whichassignsradiancetoallraysoriginatingfrom
everypointinspace.
Realizingthatsingleimagesofasceneare2Dslicesoftheplenopticfunction
andthatitcanbereconstructedfromasetoftheseslicesviaappropriateinterpo-
lationwasthemajorinsightofGortleretal.[GGSC96]andLevoy&Hanrahan
[LH96]andkicked-offimage-basedrendering.Inshort:whilerenderingbasedon
approximate,iterativesolutionsoftherenderingequationcomputesvaluesofthe
plenopticfunctionforagivenviewpoint,image-basedrenderingreconstructsthe
plenopticfunctionfromasetofsamples.
Forrenderingpurposesitisoftenconvenienttoenclosethewholescene/object
whoseplenopticfunctionisabouttobesampledinaboundingvolumeV.Then
itisassumedthattheviewerisalwayslocatedoutsidetheboundingvolume.It
resultsthattheraysoriginatingfromtheboundingvolumesurfacearesufficientto
notrepresentchangethealongcompletearay).Inplenopticcomputerfunctiongraphicsofthethisobject(insimplifiedvacuum4D-versionradianceofdoesthe
plenopticPleasenote,functionthatisitcalledisalsothepossible(outgoing)tolightplacefieldtheLvieo,V(werx,ω)inside.thebounding
volume.Thisway,theradianceenteringthevolumeisstoredwhichallowsto
renderforexamplewalk-throughanimations.Byconventiontheselightfieldsare
calledincidentlightfieldsLi,V(x,ω).

FieldReectanceThe2.5.2Lightfieldrenderingallowstovirtuallyinspectrealobjectsandwholesceneswith
previouslyunmatchedrealism.Honestly,doingimage-basedrenderingthisway
hasmoresimilaritieswithphotographythanwithrenderingsinceapartfromthe
variableviewpointtheserenderingsarecompletelystatic.Infact,image-based
renderingisperformedwithoutexplicitknowledgeofgeometryandmaterialsand
henceitisnotclearhowthesepartsofthescenecouldbealtered.
varyingDuetotheillumination:linearityofAddinglightthetransportplenopticthisfunctionsproblemofacanscenebeallelitbyviatedtwoindifcaseferentof
illuminationconditionswillyieldtheplenopticfunctionofthesceneasbeinglit
bythecombinationofthetwoilluminations.Inshort(theincomingillumination
subscript):asindicatedis

PL1+L2=PL1+PL2.

22

2.5.IMAGE-BASEDRENDERINGANDTHEBTF

Figure2.2:ThereectancefieldRVtransferseveryincidentlightfieldLi(xi,ωi)
toitscorrespondingoutgoinglightfieldLo,V(xo,ωo)parameterizedonbounding
surfaceV.Thesceneitselfcanbearbitrarilycomplex.

fLetaceusVno(seewassumeFigureag2.2).ainthatLetusthewholefurthermoresceneisassumeenclosedthatthewithinailluminationboundingonlysur-
static).originatesThenfromtheoutsideincomingthevolumeillumination(ifthecanscenecompletelyemitsbelightthisrepresentedlightwillbyanremaininci-
dentBasedlightonthefieldLi,Vlinearity(x,ωof)lightparameterizedtransportitonwtheouldsurfnoacewbeVofthepossibletoboundingcomputveolume.the
outgoinglightfieldLo,V(x,ω)foranarbitraryincidentlightfieldifwehadsome
kindincidentofraytransport(xi,ωi)functionusingRtheVthatfollowingencodesintethegral:outgoinglightfieldforeverysingle

Lo,V(xo,ωo)=RV(xi,ωi;xo,ωo)Li,V(xi,ωi)dωidxi(2.11)
VΩi+(xi)
Sincetheincidentlightfieldisdefinedoutsideoftheboundingvolumeofthe
scenethisintegralisnotrecursiveincontrasttotherenderingequations(2.1)and
(2.2).Wemightcallequation(2.11)theimage-basedrelightingequation.The
transportfunctionRVisdefinedasthereectancefield[DHT+00]anditrepre-
sentstheoutgoinglightfieldofthesceneforeverypossibleincomingillumination.
RVisprincipallyequivalenttotheBSSRDFS(Equation(2.3))butitisnotasso-
23

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

Figure2.3:TheBTFBVtransfersincomingdirectionallightingLdi,V(ωi)tothe
correspondingoutgoinglightfieldLo,V(xo,ωo)parameterizedonaplanarrefer-
encesurfaceV.Incontrasttoageneralfar-fieldreectancefieldthesceneis
usuallyanapproximatelyatsurfacebutwitharbitrarilycomplexmesoscopicge-
.ometry

ciatedwithaphysicalsurface.Instead,itisassociatedwiththeboundingsurface
Vwhichcanenclosearbitrarilycomplexsceneswitharbitrarilycomplexgeom-
etryandlighttransport.Inotherwords,whiletheBSSRDFismeanttoencode
lighttransportonasurfacethereectancefieldcanrepresenttheappearanceof
complexscenesinablack-boxmanner.

2.5.3BidirectionalTextureFunction
ThetermBidirectionalTextureFunction(BTF)wasalreadyknowninthefieldof
ComputerVisionbeforeitwasintroducedtothegraphicscommunitybyDischler
[Dis98]as"amoregeneralformulationofthetexturemappingprinciple".
ItiseasytoconfusetheBTFwithaSVBRDF(Equation2.10)whichproba-
blywouldbeamoreconvenientnameforspatiallyvaryingappearancebecause
thetermBRDFissowell-knownbuttherearesubtledifferences.First,wehave
thesamedistinctionasbetweenreectancefieldandBSSRDF:forBTFsthege-
ometryofthetexturedoesnotneedtocoincidewiththeparameterizedsurface.
Therefore,theBTFcancontainrealvisiblegeometrywithparallaxandmasking
effectswhicharenotpartoftheSVBRDFconcept.Second,theBTFisassumed
tobelitbydirectionallightwhichmeansthatsurfacepointsarenotonlyhitby
directlightbutalsobylightscatteringfromneighboringsurfacepointswhich
contradictsthedefinitionoftheSVBRDF,too.
Consequently,weproposetointerprettheBTFasa6-dimensionalreectance
fieldBVwhichisparameterizedona(typicallyplanar)surfaceVandencodes
24

2.6.IMAGE-BASEDAPPEARANCEACQUISITION

lightpositiontransportxi(farfor-fielddirectionalillumination).incidentlightTherefore,fieldsgivenwhichthedoBTFnotBvVaryofawithscenesurfaceits
fieldoutgoingLdaslightfollofieldws:Locanbecomputedforanarbitrary,directional,incidentlight
i,VLo,V(xo,ωo)=BV(ωi,xo,ωo)Ldi,V(ωi)dωi(2.12)
+ΩiTheectancerestrictionfieldtowhichfar-fieldmeansthatilluminationtheBTFcutsisatwomoredimensionslightweightfromtherepresentationfullre-
comparedtoageneralreectancefield.Onthedownsidelighttransportbetween
difplicationferentofsurfaceBTFspointsarematerialscannotbewithresolved.significantKeepingmeso-scaleinmindthatstructuresthethistypicalisnotap-
aparedhugetorestthesizerictionofthebecausemesoscopicmostofthesestructuresmaterialstheareincomingliopticallyghtisthickusuallyandslocom-wly
varying.Ofcourse,therewillbeartifactsifthematerialislitbylaser-pointer-like
spatiallyilluminationvaryingoratstructuresharpofshadotewxturesboundariesoftenhidesbutonthesethekindsotherofhandartiftheacts.complex

AcquisitionppearanceAImage-Based2.6MatrixransportTLight2.6.1Insections2.4and2.5theBSSRDFanditsimage-basedpendant,thereectance
field,wereintroducedascontinuousfunctions.Sincewewanttosamplethese
functionsandusethemeasurementsforrendering,discreterepresentationsare
needed.Therefore,wediscretizethedomainoftheincominglightfieldbydefin-
ingasetofbasisilluminationsL={li}i∈IindexedbyanindexsetI.Further-
more,wedenotebyrithediscretizedoutgoinglight-field(parameterizedbyan
indexsetK)whichisthescenesresponsetotheincomingbasisillumination
arbitrary,linearcombinationl=ililiofbasisilluminationsisgivenas
li.Then,duetothelinearityoflighttransporttheoutgoinglightfieldloforan
lo=liri(2.13)
I∈iwhichcanbewritteninmatrixform:
lo=R(K×I)l(2.14)
whereR(K×I)=[r1r2...r|I|]isthe|K|×|I|-matrixoftheconcatenatedba-
sislightfieldresponsevectorswhichisusuallycalledthelighttransportmatrix.
25

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

Figure2.4:Schematicacquisitionofthe8Dtransportmatrix.Anarrayofcameras
samplestheoutgoinglightfield.Arbitraryincidentlightfieldsaregeneratedby
projectors.ofarrayan

Equation(2.14)canbeinterpretedasthediscreteversionoftherelightingequa-
(2.11).tionfullIntransportthisrespect,matrixthebysampledassumingBTFonlycaninfinitelybedefineddistantasalighting:reducedversionofthe

lo=B(K×Id)ld(2.15)

EachcolumnbjofB(K×Id)representstheoutgoinglightfieldofthecaptured
ddbjsceneareinso-calledresponse2Dtortheeectancedirectionalfunctionslight[DHTsource+li00]-indethexyedbyrepresenti∈Ithe.Theresponserows
ofaspecificsamplefromtheoutgoinglightfieldtothevaryingbasislights.

2.6.2CapturingtheLightTransportMatrix
MeasuringR(K×I)foraspecificscenecorrespondstolightingthescenewitheach
basispropriatelightlidetector).andAhmeasuringypotheticalthedevicecorrespondingformeasuringoutgoingthelightfullfieldLTM(usingisandepictedap-
inFigure2.4.Itconsistsofasetofprojectorswhichareplacedalongahemispher-
icaldiscreteboundingsetofsurfdirectionsaceandbyareableswitchingtocasinditlightvidualrayspixels.fromThediscreteoutgoingpositionslight-fieldintoa
iscapturedbyperspectivecamerasplacedalongthesameboundinghemisphere.

26

2.6.IMAGE-BASEDAPPEARANCEACQUISITION

Whileitseemspossibletobuildsuchasetupphysically,aquickcalculation
suggeststhatadensesamplingofR(K×I)seemsoutofreach.Assumingareason-
ablehemispheresamplingresultsof512ina×512transportmatrixprojector/camerawithpixaboutels(2.and68∙3210×8)322entries!positionsonthe
Therefore,mostresearchersconcentratedonmeasuringslicesofthefull8D
transportmatrix.Capturingonlytheoutgoinglightfieldforonefixedillumination
(|I|=1)isthemostcommoncase(e.g.[LH96,GGSC96,MRP98,WAA+00]).In
their2seminalpaperLevoy&Hanrahancapturedbetween256and2048imagesof
256pixelresolutionwhichtookupto4hoursofacquisitiontime.Anotherwell-
known4DsliceiscapturedbythefirstLightStagefromDebevecetal.[DHT+00].
Theyassumeddirectionallightingandafixedviewpoint.Usingarotatablelight
armandavideocameratheywhereabletocaptureabout64×32differentlight
minute.oneindirectionsThefirstworkwhichdealtwithnear-fieldilluminationwaspublishedbyMas-
selusetal.[MPDW03].Theyusedprojectorstogenerate224×256=57344
differentbasisincidentlightfieldswhichtookmorethan100hourstocapturefor
.wviesingleaBythetimeofwritingthisthesistheonlyworkwhichtriedtotacklethefull
problemisbyGargetal.[GTLL06].Theyusedonlyavarysparsedirectional
sampling(3×3directionswhichcoveronlyasmallsectorofthehemisphereand
130×200pixelspatialresolution)andexploitedahierarchicalrepresentationof
thetransportmatrixtoreducetheactuallyrequirednumberofsamplesbytwo
ordersofmagnitude.Whiletheirresultsarealreadyimpressivejustextendingthe
setuptocoverthewholehemisphereofdirectionswouldresultinmeasurement
timesintherangeofweeks.

AcquisitionBTF2.6.3BTF-Measurementfitsintothegenerallighttransportacquisitionframeworkfrom
lightFigure2.4sources.withtheTherebydif,theferencethatacquisitionthelightcomplexityprojectorsisarereducedreplacedbytwobydimensions.directional
Furthermore,thesamplesareusuallyalmostplanarwhichsimplifiestherequired
calibrationandregistrationproceduressignificantly.
TheBTFmeasurementsusedinthisthesishavebeencapturedbytwodifferent
measurementdevicesbuiltattheUniversityofBonn.
ter-likTheefirstconfigurationsetup,publishedwhichinmeans[SSK03],lightissourcebasedandonadetectorclassicalcanbeplacedgonioreectome-freely
onthehemisphereabovethesample.Itisrealizedbyplacingthesampleona
robot-armwhichmovesandrotatesthesampleinspace.Thelightsourceisan
HMIbulbplacedabout2.5mawayfromthesampleinordertoachieveapproxi-
matelydirectionallighting.Thecamera(aKodakDCSPro14M)ismountedon

27

CHAPTER2.PRELIMINARIESOFVISUALAPPEARANCE

θ[◦]Δφ[◦]#images
015−6061
123030182045756015182024

Figure2.5:Thegonioreectometer-likesetupatUniversityofBonn(left).The
samplingoftheviewingandilluminationanglesofthemeasurementsusedinthis
thesissumsupto81anglesforeachhemisphere(right).

Whilehalf-circletherailsetupatinaboutprincipletheallosamewsdistancearbitraryfromsampltheingsofsamplethe(seelightingFigureand2.5viewingleft).
Figuredirections2.5allwhichresultsmeasurementsin81usedindirectionsthisperthesisarehemisphereusingtheandthussamplingin6561depictedimagesin
measurement.completeafor+acquisitionThesecondprocesssetupbywasusingapublishedsetofincheap[RMSconsumer08].Itcamerasaimsatinparalspeedinglel.upInthethe
onarealizedvhemisphericalersion151aluminumcamerasgwithantrya.Figureresolution2.6ofsho3.2wsamegapixphotographelswereofthemountedsetup
80andcmgivesandthethebuipositionslt-inofashthelightscameras.areemploTheyedradiusasoflightthesources.hemisphereDueistoaboutthe
berelativelydirectionalshortwhichdistancerequiresfromathecorrectionsamplethesteplightaftersourcesmeasurement.cannotbeassumedto
DiscussingfurtherdetailsandpracticalissuesoftheseBTFmeasurementde-
vicesstate-of-the-artliesnotwithinreporttheaboutscopeBTFofthesiacquisition,s.Wesynthesisrefertheandinterestedrenderingreader[MMS+to05].the

28

2.6.IMAGE-BASEDAPPEARANCEACQUISITION

θ[◦]Δφ[◦]#images
1−066011123023.5123030123037.5182045182052.5241560241567.5241575

Figure2.6:TheparallelBTFacquisitiondevicebuiltatUniversityofBonn(left).
shoThewndeinvicetheconsiststableonofthe151right.camerasSincewhichthebareuilt-inarrangedashlightsontheareusedhemisphereaslightas
sourcesamaximumof151samplescanbemeasuredforeachhemisphere.

29

C

HAPTER2

30

.

P

RELIMINARIESOFV

ISUALA

P

P

E

A

R

A

N

C

E

artP

I

Compression

31

CHAPTER3

BACKGROUND

Thestoragerequirementsofuncompressedmeasuredappearancedataeasilyex-
ceedseveralgigabyteswhichmakescompressionabasicnecessityofanyimage-
basedrenderingsystem.Suchcompressiontechniquesshouldnotonlyallowhigh
compressionratioswhilemaintainingmostofthevisualfidelityoftheoriginal
ing.databutalsoUnfortunatelyafast,theandrwell-knoandomwnaccesstechniquesdecomprfromessionthestepfieldofforefimageficientandrendervideo-
compressiondonotfulfillthesedemands.
Forexamplewithlosslesscompressiontechniquesbasedonentropycoding
[Sha48]compressionratiosofabout3:1canbeachieved(cf.Figure4.1)which
isobviouslynotsufficient.Applyingsophisticatedlossyimagecompressional-
gorithmsliketheonesusedwithintheJPEGorJPEG2000standardstoasingle
oracompressionblockofstageimagesistooesoundsxpensivattractieforvebutrenderingisinfactapplicationsimpractical,andthesinceachiethevablede-
compressionratiosofabout1:20arestillnothighenoughconsideringrawdata
sizesofseveralGBs.
Inordertoachievetheabovegoalsso-calleddomainspecificalgorithmsare
andrequiredinwhichparticularexploitBTFthedata.specialThehugestructureamountandofpropertiesliteratureofinthisimage-basedareacandatabe
roughlycategorizedintothreedifferentgroups:
Parametricmodeling-adaptingideasfromBRDF-and/ortexturemodelingto
datareectancearyingvspatiallyBasisprojection-usingsuitablebasisfunctionslikemulti-dimensionalWavelets
HarmonicsSphericalorStatisticaltionsdatausinganalysistechniques-likecomputationPrincipalofComponentcustomized,Analysisdata-driven(PCA)basisfunc-
definedExistingbasistechniquesfunctionbasedwillonberevieparametricwedinmodelingChapterand6.Inbasisthisandprojectiontheusingfollowingpre-

33

CHAPTER3.BACKGROUND

chapterwewillfocusonthelattergroupwhichisstatisticaldataanalysis.Within
thisgroupwewilldiscussthosetechniqueswhichbasicallyboildowntotheap-
plicationofmatrixfactorizationalgorithmstothelighttransportmatrices(2.14)
and(2.15)whichexplainsthetitleofChapter4.
Amainadvantageofthesetechniquescomparedtoparametricmodelingand
fixedbasisfunctionsistheirgreatergeneralityandeffectivenessthankstothe
functions.basisenvdata-driGeneralityinthiscontextmeansthatthebasisisadaptedtotheparticular
datasetandthatincontrasttoparametricmodels,whichareusuallydesignedto
modelaspecificclassofmaterials(e.g.uniformmetalsorplastic),almostnore-
strictingassumptionsaboutthematerialclassesthatcanberepresentedaremade.
Infact,itisonlyassumedthatthedatamatrixhasasimplecovariancestructure
whichmeansacovariancematrixoflowrank.
Thereby,thesemethodsarenotonlygeneralbutalsoeffectivesinceincontrast
tousinga-priorifixedbasisfunctionslikeSphericalHarmonicsthedata-drivenba-
sisadaptstothedatawhichusuallyenablesbettercompressionratiosandlower
runtimereconstructioncosts.Sinceincontrasttoafixedbasisthedata-drivenba-
sishastobestoredtogetherwiththecoefficientsthereisanoverheadinvolvedbut
thisoverheadisusuallymorethancompensatedbythelesscoefficientsrequired.
However,itisalsonotcleara-priorithatthelighttransportmatricesingeneral
haveasimplecovariancestructureandthatfewcustombasisfunctionssufficefor
anefficientapproximation.Infact,simpleempiricaltestsshowthatforcompli-
catedmaterialstheEigenvaluesofthecovariancematrixdecreaseslowlywhich
suggeststhatspatiallyvaryinglighttransportingeneralisahigh-dimensional
phenomenon.Furthermore,thecomputationofthedata-drivenbasisfunctions
canposeaseriouscomputationalchallengebecauseofthehugesizeofthedata
matrix.Asaresultseveralvariantsofthebasicmatrixfactorizationschemehave
beenintroducedovertheyears,amongthemcombinationsoffactorizationand
clustering(e.g.[MMK03])andtensorfactorizationtechniques(e.g.[WWS+05])
whichessentiallycorrespondtotheapplicationofmatrixfactorizationtodifferent
subsetsandarrangementsofthedata.
Inthispartofthethesiswewillcomparevariousofthesedifferentfactoriza-
tiontechniquesintermsofcompressionratio,reconstructionqualityandrun-time
decompressioncost.Additionally,wealsoanalyzetheperformanceoftwo-way
clusteringofmatrixelementswhichhasnotyetbeenappliedforBTFcompres-
sion.Furthermore,inChapter5weintroduceData-DrivenLocalCoordinateSys-
tems–atechniquewhichimprovesthecorrelationbetweenrowsandcolumnsof
thedatamatrixbyestimatinglocalframespersurfacepoint.Thisimprovescorre-
lationandresultsinadecreasedrankofthecovariancematrixwhichthenresults
inanimprovedcompressionratioofmatrixfactorizationtechniques.
Intheremainderofthisbackgroundchapterweprovidethetheoreticalfoun-

34

3.1.MATRIXFACTORIZATION

dationsapplicationofmatrixareaand(compressiontensorfaofctorizationimage-basedtechniquesmeasurements).independentlyofourspecific

actorizationFMatrix3.1Matrixfactorizationordecompositionisaquitegeneralconceptfromlinearalge-
bra.InitsgeneralformafactorizationofthematrixAisaproductoftheform
KA=Fi.
iThekeyroleofmatrixfactorizationsinnumericalcomputationsstemsfromthe
ftrixactthatproblems.factorsAoffamspecialousexamplestructureiscanthehelpLU-factorizationtremendouslyforininvsolvingertiblecertainmatricesma-
fwhereactorizationA=canLUbeandusedListoloefwerficiently-triangularsolveandlinearUisequationsupperAx-triangular=.LUxThe=LU-b
withoutgaussian-eliminationsimplybyforwardandbackwardsubstitution.If
thelinearsystemhastobesolvedseveraltimesfordifferentbthecostforthe
amortizes.quicklyitselfactorizationfTheimportanceofmatrixfactorizationsfordatacompressioncomesinthe
formoftheSingularValueDecompositionwhichwillbediscussedinthefollow-
iningfactcansubsectionbeusedwherewesynonwillymouslyalsogivinethecaseofrelationmean-centeredbetweenSVDdataandmatPCArices.whichAs
mentionedintheintroductionthelighttransportmatrixgenerallyhashighrank
whichimplieshighstoragerequirementsandreconstructioncost.Furthermore,
thefactorizationofhugematricescanposeahugecomputationalchallenge.This
motivatesblockwise-andclusteredfactorizationtechniqueswhichaimatfinding
localeralizeslow-rankmatrixfactorizationapproximations.tohigherAnotherdimensionaltrendistensorarrangementsfactorizationofdata.whichTherebygen-,
redundanciesalongthisadditionaldimensionscouldbeexploited,eventuallyre-
sultinginamorecompactfactorization.

DecompositionalueVSingular3.1.1BecauseofitsfundamentalimportancewewillgivetheSVD-theoremhere.We
assumethatthereaderisfamiliarwiththebasicconceptsfromlinearalgebralike
rank,eigen-valuesandeigen-vectorsaswellasunitaryanddiagonalmatrices.
(SVD)3.1.emTheorIfA∈Rm×nhasrankk,thenitmaybewrittenintheform
TUSV=A35

CHAPTER3.BACKGROUND

whereU∈Rm×mandV∈Rn×nareunitarymatrices.ThematrixSisa
m×n-diagonalmatrixwithsii≥si+1,i+1>0for1≤i<kandsii=0for
k+1≤i≤min(Tm,n).ThenumberssiiarethenonnegativesquarerTootsofthe
eigenvaluesofAA.ThecolumnsujofUTaretheeigenvectorsofAAandthe
columnsvjofVaretheeigenvectorsofAA.
ForaproofofTheorem3.1werefertheinterestedreaderto[HJ86,p.415].
ThecrucialpropertyoftheSVDfordata-compressionisnowgivenbytheEckart-
Theorem:oungYoung)(Eckart-Y3.2.emTheorLetUSVTbetheSVDoftherank-kmatrixA∈Rm×nasgiveninTheorem3.1.
Furthermore,wedefineforr≤ktherank-rapproximationArofAasfollows:
rAr:=ujsjjvTj
jThenAristhebestrank-rapproximationofAintheleast-squaressense:
mn
jiAr=raargnk(Bmin)=r|A−B|Fwith|C|F=c2ij
Proof.ThekeyisthattheFrobenius-norm|•|Fisunitarilyinvariant:
|UAVT|F=|A|FifUandVareunitary.AfterTheorem3.1theSVDofA=
USVTexistsandwehave:
|A−B|F2=|S−UTBV|F2
TSinceSisadiagonalmatrix,foranyminimizerof|A−TB|F2thematrixD=
UBVmustbeadiagonalmatrix,too.Therefore,UDV=Bisthesingular
valuedecompositionofB.SinceBoughttobeofrankr,Dhasonlyrnon-zero
ws:folloItentries.rank(minB)=r|A−B|F2=|S−D|F2=dii,0min<i≤r(sii−dii)2+sii2
rn
+1r=iiwhichimpliesdii=siifor0<i≤r.
AnobviousapplicationofTheorem3.2isdatacompressionsincetheoriginal
storagerequirementsofO(mn)canbereducedtoO((m+n)rr)whichrresultsin
significantsavingsifrm,nsincethecompressionratiois(n+m).
36

3.1.MATRIXFACTORIZATION

Figure3.1:Factorizingamatrixintoasumofouter-products(rank-1matrices).

Thepricetobepaidisthereconstructionerrorin=r+1sii2whichcanbein-
terpretedasthevariancenotcapturedintherank-rapproximationsinceasgiven
abovethesiiarethesquarerootsoftheeigenvaluesofthecovariancematrixAAT.
sumofGenerallyouter,weproductscanstate(rank-1thatamatrices)matrixasAcanillustratbeedwellinFigurereconstructed3.1ifbytheaeigen-short
valuesofAATdecayfast,i.e.thecorrelationbetweentherows/columnsofAcan
beconsideredsufficientlyhigh.Pleasenote,thatcomputingtheSVDofA˜where
thecolumnmeana¯=n1inaiissubtractedfromeachcolumnisequivalentto
performingaprincipalcomponentanalysis(PCA,seee.g.[Jol86])onthecolumn
vectorsofA.InthiscaseUisthematrixofeigenvectorsandSVTisthema-
trixofPCA-weights.Inthefollowingwewillalwaysassumemean-centereddata
matrices.ThecomputationoftheSVDisusuallyperformedbycomputingthesymmet-
ricroworcolumncovariancematrixAAT∈Rm×morATA∈Rn×ndepending
onwhichissmaller.Thenaneigen-decompositionalgorithmforsymmetricma-2
IftriceswelikeassumethetheJacobicasemmethod<ncanthenbeVTusedcantobecomputecomputedUorbyVVT=respectiS†vUelyTAandwhereS.
S†denotesthepseudo-inverseofS.
ThecomplexityforcomputingthecovarianceisO(m2n),thediagonalization
requiresO(m3)andthecomputationofVO(rnm)operationsifonlythefirstr
complecolumnsxityofisVareboundedcomputed.bythecostSinceofwethecoassumedvariancem<nmatrixtheoverallcomputation.factorizationThere-
fore,numerousapproximationalgorithmshavebeendevelopedwhichtrytoavoid
thisPCAcostly[Row98]step.whichExamplescomputeareOnline-SVDapproximate[Bra03]representationsoroftheExpectation-Maximization-orthogonalized
sub-spacesiteratively.ThesealgorithmshaveusuallyacomplexityofO(rnm)
whichleadstohugecomputationalsavingsifrissmallwhichisusuallythecase

37

CHAPTER3.BACKGROUND

incompressionapplications.InourpracticalexperimentsweusedEM-PCAbe-
causeofitseaseofimplementationandnumericalstability.WealsotriedOnline-
SVDwhichbehavessimilarlyintermsofstoragerequirementsandcomputational
complexitybutithasthedisadvantageofrequiringathresholdparameterwhich
decidesifthecurrentsubspacehastobeextendedandwhichturnedouttobe
difficulttochooseappropriatelyinpractice.

actorizationFiseBlock-W3.1.2tion.ApplyingAcommonSVDtotheapproachcompltoeteachievmatrixeloAwercanrankbefinterpretedactorizationsasofalarglobalgematricesfactoriza-is
toperformalocalorblock-wisefactorizationbypartitioning+thematrixintosub-
blockswhicharefactorizedindependently(e.g.[MPN02,CBCG02,MMK03,
haveNBB04,alowerNNJ05,rankthanGTLL06]).thewholeUsuallymatrix.,itIncanfact,beithasassumedbeenthatshowntheseinsub-blocks[MSRB07]
thatmatrixthereandisthelinearspatialrelationshippatchsize.betweenThevtheariousdimensblock-wiseionalityofmatrixtheflightactorizationtransport
selecttechniquesandorgusedanizeincompressionmatrix-blocks.ofWewillimage-basedpresentdatathesediffertechniquesmainlyinintheawaycommonthey
Itnotationalisconvframeenientworktofordefineblockwhatwematricesmeanfollowithwinga[Hac99].partitioning:
artitioning)(P3.1.DefinitionjLet≤Ipbe}a⊂Pfinite(I)inde\{∅}xisseta(e.g.Ipartitioning={1,..of.I,nif})with|I|=n.ThenP1={Ij:1≤
nIi∩Ij=∅pfori=j
nI=j=1Ij.
Thecorrespondingj-thvectorblockofavectora∈Rnis(ai)i∈Ij
doItnotisneedtoimportantconsisttoofnotethatconsecutiveaccordingelements.tothisTheydefinitionjusttherepresentindexanblocksarbitraryIj
groupingofindexelements.InordertofindtheblockIjcontaininganindex
elementpartitioningiwehavgeneralizesetostorethisaconceptblocktoindexper2-dimensionalelementinindethexsets:generalcase.Block
Definition3.2.(BlockPartitioning)
LetI,Jbefiniteindexsetswith|I|=mand|J|=n(e.g.I={1,...,m}and
38

3.1.MATRIXFACTORIZATION

J={1,...,n}).ThenP2={bj:1≤j≤p}⊂P(I×J)\{∅}isablock
partitioningofI×Jif
bi=I˜×J˜withI˜⊂IandJ˜⊂I
bi∩bj=∅fori=j
pI×J=bj.
=1jThematrixblockofamatrixA∈Rm×ncorrespondingtobk∈P2isgivenas
(aij)(i,j)∈bk
ThisdefinitionallowstopartitiontheindexsetI×Jintoarbitrary,rectangular
blocks-theyjusthavetocoverthewholeindexsetandarenotallowedtooverlap.
Again,inthegeneralcasewehavetostoreablockindexperindexelementin
ordertofinditscontainingblockinconstanttime.Therefore,inpracticemore
restrictedblockschemesareusedwhichminimizetheoverheadforstoringand
accessingtheblockstructure.Wewillnowshortlyintroducethemostcommon
schemesinorderoftheircomplexitywhichareregularblocksandtensor-product
.ksblocDefinition3.3.(RegularBlockPartitioning)
LetthefiniteindexsetsI,Jwith|I|=mand|J|=nandcorrespondingparti-
tioningsPIandPJbegivenaccordingtoDefinition3.1.Thentheblockpartition-
ingPr={Ii×Jj:Ii∈PI,Jj∈PJ}isaregularblockpartitioningifthereexist
twointegersmbandnbsuchthatpm=m/mbandpn=n/nbareintegersand
|Ii|=mbforIi∈PI
|Jj|=nbforJj∈PJ
Ifmmodmb=0ornmodnb=0thenthereexistsalsoonepartIi0∈PIwith
|Ii0|=mmodmboronepartJj0∈PJwith|Jj0|=nmodnbrespectively.
Usually,itisassumedthattheindexsetsareorderedandthepartitionsPIand
PJcontainconsecutiveelements(max(Ii)<min(Ii+1)).Inthiscasetheblock
indexforanindexelement(i,j)canbecomputedsimplyas(i/mb,j/nb).
Thenumberofblocksisgivenbypm×pn.IfSVDisnowappliedtoeach
blockasillustratedinFigure3.2andasinglerankrbischosenforallblocksthe
storagerequirementsaregivenbyO(pmpn(mb+nb)rb).
Regularblockswithconsecutiveelementscanbeaccessedinconstanttime
whichleadstoO(rbp)mpnreconstructioncostpermatrixelementandthecompression
ratioisgivenbyrb(m+n).

39

CHAPTER3.BACKGROUND

dentlyFigure3.2:approximatedPrinciplebyoffaloactorizingw-rankfregularactorization.blocks:Eachregularblockisindepen-

Itcaneasilybeseenthatrb∙pmandrb∙pnhavetobeintheorderofrifthe
compressionratioshouldbecomparabletostandardfactorization.Ifreconstruc-
tioncostisofmoreprominentimportanceaslightlyworsecompressionratiocan
beacceptedifrbisonlylowenoughsuchthatacertainrenderingperformanceis
achieved.Forexample,inthecaseofpm=pn=10,rbmustbeintherange
of0.1rtoreachthesamecompressionratio.Iftheresultingreconstructioner-
roristoohighweprobablymightneedtodoublethenumberofcomponentsand
hencedoublethememoryrequirementsbuteventhenthereconstructioncostwill
beapproximatelyfivetimeslowercomparedtostandardSVD.
Thecomputationalcomplexityofblockfactorizationissimilartostandard
factorizationifanapproximationalgorithmlikeRoweisEM-algorithmisused
section).viouspre(cf.Whileasignificantrankreductioncanbeachievedalreadybysimpleblock-
wisefactorizationithastobenotedthattheblocksizeandpositionarefixedbe-
forehand.Oneproblemofthisapproachiswell-knownfromblock-basedimage-
orvideocompressiontechniqueslikeJPEGorMPEG-2:theregularbordersbe-
tweentheindependentlyapproximatedblocksareeasilyspottedasblockartifacts
inthereconstructedimages.Anotherproblemisthatapossiblygreatdealof
coherencebetweenelementsfromdifferentblocksisnotexploited.
Byrelaxingtherestrictionofafixedblocksizetensor-productpartitionings
allowbetteradaptionofblockshapesandsizestothedata:

Definition3.4.(Tensor-ProductPartitioning)
LetthefiniteindexsetsI,Jwith|I|=mand|J|=nandcorrespondingparti-
tioningsPIandPJbegivenaccordingtoDefinition3.1.Thentheblockpartition-
ingPr={Ii×Jj:Ii∈PI,Jj∈PJ}isatensor-productpartitioning.

40

3.1.MATRIXFACTORIZATION

Figure3.3:Principleofadaptivefactorizationusingonlycolumnpartitioning:a
thecolumncolumnspartitionofAPtoJgetisthecomputedmatrixof(herethefaconcatenatedsymbolizesablockmatrixmatriceswhichAJi).permutesThen
theblockmatricesAJiarefactorizedindependently.

Ofcourse,theregularblockpartitioningisaspecialcaseofthetensor-product
partitioningwithconsecutiveblocksofequalsize.Generaltensor-productblocks
areofvaryingsizeandtheirpartialrowsandcolumnscanbescatteredacrossthe
wholematrix.Therefore,findingtheblockofagivenmatrixelementgenerally
requirestostorearow-andcolumnblockindexfortheelementsofthepartitions
PIandPJwhichrequiresO(m+n)storagespace.Thenthetensor-productblock
indexcanbelooked-upinconstanttimeandthereconstructioncostremainsO(rb)
ifagainafixedrankrbpersubmatrixisused.
Givenanumberofrowpartitionspm=|PI|andanumberofcolumnpartitions
pn=|PJ|thestoragerequirementsfortensor-productblockfactorizationare
similartotheregularblockcaseandthecompressionratioisapproximatelythe
same(uptotheblockindices).Thecomputationalcomplexityforthefactorization
aloneremainsO(mnrb)ifaniterativemethodisused.

ContentMatrixtoBlocksAdaptingThecanbeadvantageadaptedoftothetensormatrix-productcontent.blocksWewillcomparedcalltotheseregularkindofblocksblockisthatschemesthey
adaptive.Ideally,wewanttofindpartitionsPIandPJwhichareoptimalinterms
ofreconstructioncost,reconstructionerrorandstoragerequirements.Unfortu-
nately,thenumberofpossiblepartitionsofanindexsetIofsizenisgivenby
theBell-numbersBn[Com74]whichgrowsuper-exponentially(E.g.asetof20
hopeelementstofindhassuchalreadypartitionsmorebythane51xhaustitrillionvesearch.possiblepartitions).Hence,wecannot
Inpractice,somefeasibleerrorcriterionisdefinedandthenclusteringalgo-
rithmsareusedtominimizethismeasure.Ifweallowtopartitiononlythecol-
41

CHAPTER3.BACKGROUND

ofumnclusteringspace(|aPI|set=of1)nasmillustrated-dimensionalindataFigurev3.3ectors.wehaUponvethetheclassicalnumerouseproblemxisting
thealgorithmsmostpopularforsolvingone(atthisleastforproblemathequadratick-meanserroralgorithmcriterion).[Mac67]isprobably
knownTheinmorethegeneralliteratureasproblemtwo-wayof-orcosimultaneously-clusteringandclusteringithasrobeenwsandstudiedcolumnsmainlyis
inthefieldofbioinformatics,inparticulargeneexpressionanalysis(e.g.[GLD00]
[DMM03]).theTobasisthisofendthewek-meanswillonlyalgorithm.detailoutItthecomputesclassicalalocalone-wayminimumclusteringoftheapproachfollowingon
2costfunction:pn
EPJ=i=1j∈Ji(aj−a¯Ji)(3.1)
wherea¯Ji=j∈Jiaj/|Ji|isthemeanofthecolumnblockJi.Typically,alocal
minimumof(3.1)iscomputedusingLloydsalgorithm[GG91].Thenmatrix
blocksAJicanbecollectedandSVDcanberappliedtoeachofthem:
bAJi=(aj)j∈Ji≈uJi,jwJTi,j(3.2)
=1jTheconstructionstandarderrorink-meanstheerrorclusteringfunctionasapproachproposedcanbybeimproKambhatlavedbyandusingLeenthe[KL97]:re-
pnrb2
EPJ=i=1aj−a¯Ji−aj−¯aJi,uJi,kuJi,k(3.3)
j∈Jik=1
InreplacedthiscasebythethefactorizationcomputationofofthetheblockcentroidmatinrixtheA.InclassicalorderLlotoyditinitializeerationtheis
JiperThe-blocktimesubspacescompleaxityfewofasistandardngleLloLloydyditeiterationsrationcanareeasilyperformed.beestimated:Every
datapointhastobecheckedagainstthepnclustercentersorsub-spacesrespec-
tiThevelyperwhich-clustersumsupsubspacestoO(havnmpeton(berb+1))recomputedoperationsineach(rb=iteration0forbasicwhichhask-means).com-
plexityO(nm(rb+1))withrbasabove.Despitethefactthatinthegeneralcase
afastconvergencecannotbeguaranteed(findingtheexactsolutionofEquation
3.1isNP-hard)thenumberofiterationsactuallyneededisusuallyquitelowin
practice.

3.1.3Two-passFactorization
blocksWhileitbyisclusteringpossibletotherereducewilltheusuallycoherenceremainsomebetweensortofindependentlyredundancyfactorizedbetween

42

3.1.MATRIXFACTORIZATION

Figurecolumn-space3.4:Twbasis)o-passffromeachactorizationblocksimplyandtakappliesesallanbasisadditionalvectorsf(inactorizationthiscasestep.the

thesubspaces.InordertoexploitthisredundancyNayaretal.[NBB04]proposed
toperformasecondfactorizationpassonthebasisvectorsofthealreadycomputed
subspacesasillustratedinFigure3.4.Themotivationisthatifaregularblock
partitioningisusedredundancybetweenblockswillberatherlikely.
Wewillformulatethemethodbasedonasimpleblockschemewithmbrows
per-blockandpm=mmbblockswhichisinthespiritoftheoriginalpaper.Weomit
thestraight-forwardgeneralizationtoageneralblockschemehereforbrevity.
FactorizingeachblockAb∈Rmb×nyields
Ab≈U˜bW˜bT
withU˜b∈Rmb×rbbeingthereducedorthogonalblockcolumnbasisandW˜b=
V˜bS˜b∈Rn×rbbeingtheweightmatrixdescribinghoweachcolumnwillbere-
constructed(reducedorthogonalblockrowbasistimessingularvalues).
Concerningstoragerequirementsitcanbeimmediatelyobservedthatthis
typeoffactorizationneedstostoreafullrowbasisforeveryblockleadingto
O((m+npm)rb)storagerequirements.Ifweassumethatthereisredundancy
betweenrowsoverthewholematrixtherewillmostlikelybealsosomeinter
row-baseredundancywhichmeansthatthematrixX∈Rn×rb∙pm,whichisthe
43

CHAPTER3.BACKGROUND

concatenationofallperblockweightmatrices,hasalow-rankrepresentation:
X≈˜YZ˜T
withY˜∈Rn×sandZ˜∈Rrb∙pm×s.Thiswaythetotalstoragerequirementsare
reducedtoO(mrb+(n+pmrb)s)whichpaysoffifnandpmrbarelargecompared
.tosThepricetopayistheincreasedreconstructioncostsincetheweightmatrix
W˜b=Y˜Z˜bThastobereconstructedduringrun-timewhichleadstocostsof
O(rbs)persinglematrixelement.

actorizationFensorT3.1.4Allments.fSinceactorizationimage-basedtechniquesmentionedmeasurementssofarusuallyoperatehaveonahigher2D-matrixdimensionalityofmeasure-the
thedatadiscreteelementsBTFhavetotransportbesqueezedmatrixinsomehoEquationwinto2.15,thisfor2Dinstance,corset.sThehoweddefinitiononewayof
howInthisthecancontebextdoneoffordatathecompression6-dimensionalthisBTF.approachhastheconsequencethat
esomexampleintrathe-rowtypicalorw-columnayofarrangingcorrelationsanareimagenottakensequenceintointoaccount.amatrixConsiderwhichforis
toandunrolltheconcatenatingrowsandthesevcolumnsectorsofintoeachamatrix.singleIfSVDmeasurementisappliedimagetointothisavmatrix,ector
intra-imagecorrelations,likethecorrelationsbetweentherowsandcolumnsof
theimages,arenotfullyconsidered.Asdemonstratedabove,theproblemcan
bealleviatedusingblock-wisefactorizationtechniques(whichtrytominimize
thecorrelationsbetweenblocks)butalsothesetechniquesrelyontheoriginal2D
data.high-dimensionaltheofarrangementTheinasensemorenaturalsolutionherearetensors.Theideaistoarrange
thedatainmulti-dimensionalgridswhichnaturallygeneralizethefamiliarma-
trixconcept.Forinstanceathree-dimensionaltensorcanbeeasilyimaginedby
humansasa3D-datacube.Moreformally,anN-thordertensorisdenotedin
calligraphicletterasA∈RI1×I2×...×INwithIn∈N+denotingthesizeofeach
dimension.ElementsofAareaccessedusingN-dimensionalindextuplesand
ifdenotedthereeasxistsai1a...inlo...iNw-rankwithf1≤actorizationin≤Iofn.generalThequestiontensorsnowhichwfulfillsimmediatelyoptimalityarises
criteriasimilartotheSVDformatrices(whichcanbeinterpretedas2ndorder
sorstensors).hasnotThebeenanswerfoundisthatyet,banutequivfortunatelyalenttothethereareEckart-Yalgorithmsoungtheoremwhichatforleastten-
offindalocalimage-basedoptimum.renderingAmongandthecompressionmostpopularistheofhigherthese-orderalgorithmsSVDinthe(HOSVD)field
basedonN-modeSVDandanalternatingleast-squares(ALS)method[LMV00].
44

3.1.MATRIXFACTORIZATION

Wewillintroduceonlythebasicdefinitionsfrommulti-linearalgebraneeded
fortheformulationofthealgorithmandrefertheinterestedreaderto[LMV00]
and[WWS+05]foranyfurtherdetails.Theconceptsweneedtoknowarethe
mode-nvectorsandmatricesofatensoraswellasthemode-nproductofatensor
matrix.aandDefinition3.5.(Mode-nvector,mode-nmatrix)
Themode-nvectorvofatensorAisanIn-dimensionalvectorconsistingofthe
elements(ai1...in...iN)1≤in≤InofAwhereonlytheIn×inde(I1∙xI2i∙n...∙In−varies1∙Ii+1∙...while∙IN)allother
indicesstayfixed.Themode-nmatrixA(n)∈Rconsists
ofallmode-nvectorsandcanbeinterpretedastheatteningofthetensoralong
dimension.-thnitsDefinition3.6.(Mode-nproduct)
Themode-nproductbetweenatensorA∈RI1×I2×...×INandamatrixU∈
givenbybi1...in−1jnin+1...iN=inai1...in...iNujninandcanbeexpressedintermsof
RJn×InisatensorB=(A×nU)∈RI1×...×In−1×Jn×In+1...×IN.Itsentriesare
attenedmode-nmatricesasB(n)=UA(n).
WecannowformulatetheclassicalSVDwithinthetensorframework.The
matrixA∈RI1×I2isasecondordertensorwithtwomodes.Thefirstmodeis
associatedwiththecolumnspaceofAwithdimensionalityI1.ItholdsA(1)=A.
ThesecondmodeisassociatedwiththerowspaceofAandhasthedimensionality
I2.Themode-2TmatrixofAequalsthetransposeofA:A(2)=AT.TheSVD
A=USVcannowbeunderstoodasadecompositionthatorthogonalizesthe
column-androw-spaceofAviathematricesU∈RI1×J1andV∈RI2×J2and
canbewrittenintermsofmode-nproductsasA=S×1U×2V.Analogously,
wecannowdefineadecompositionofageneraltensorwhichorthogonalizesthe
vectorspacesassociatedwitheachmode:
Definition3.7.(N-modeSVD)
GivenageneraltensorwithA∈RI1×I2×...×INwithN>2theorthogonalcolumn
spaceofeachmode-nmatrixA(n)canberepresentedbyanunitarymatrixUn
whichcanbecomputed,e.g.usingtheSVDofA(n).Thenthedecomposition
A=Z×1U1×2U2...×NUN
iscalledtheN-modeSVDofA.ThetensorZ,whichisgivenby
Z=A×1U1T×2U2T...×NUNT
governstheinteractionbetweenthemodesandistermedcoretensor.
45

CHAPTER3.BACKGROUND

ThecoretensorrepresentstheanaloguetothesingularvaluematrixSincon-
ventionalSVD.Unfortunately,Zusuallydoesnothaveasimplediagonalstruc-
turebutisafulltensor.Aso-calledrank-(R1,R2,...,RN)approximationA˜of
A,whichmeansrank(A˜(n))=Rn≤rank(A(n))for1≤n≤N,cannoweasily
beachievedbytruncatingthemodesUnsuchthatU˜n=(un,i)1≤i≤Rnwhereun,i
isthei-thcolumnofUn.Asalreadyindicatedthisstraight-forwardwayofreduc-
ingthedimensionalityofatensorisgenerallynotoptimal,i.e.itdoesnotyield
aglobaloptimumoftheapproximationerror||A−A||˜,butitworksreasonably
[VT04].practiceinwellAsproposedin[LMV00]theapproximationcanbefurtherimprovedbyus-
inganALSalgorithm.ThealgorithmimproveseachmodematrixU˜nitera-
tivelybyprojectingthetensorontoallrankreducedmodesexceptn:M=
A×1U˜1T×2...×n−1U˜nT−1×n+1U˜nT+1×n−2...×NU˜NT(n).Thenthematrix
MisorthogonalizedusingSVDandU˜nnewissettothefirstRncolumnsoftheleft
singularmatrixofM.Thisstepisrepeatedforallmodesanditerateduntilcon-
vergencewhichcanbedeterminedforexamplebytheamountofimprovementin
approximationqualitybetweenconsecutivesteps.
areO(nNRn)forthecoretensorandO(nNInRn)forthemodematrices.While
Thestoragerequirementsforarank-(R1,R2,...,RN)tensorapproximation
thesignificantoverheadofthecoretensorstorageisnotrequiredinthematrix
case,itstillcanbeexpectedthattheper-moderanksRicanbechosenrelatively
small.Furthermore,themodedimensionsInwillbemuchsmallerthanthematrix
dimensionswhichconsiderablyreducesthestoragerequirementsforthemode
matricescomparedtotheEigenvectorsandweightsinthestandardSVDcase.
then-thmatrixhasthedimensionsIn×kN=nIk.Usinganapproximational-
ComputingtheHOSVDofatensorrequiresdecomposingNmatriceswhere
gorithmlinearinthenumberofmatrixelements,wehavetoperformNtimes
theworkofastandardSVDwhichisO(kN=1IkRn).Itisoftenarguedthatten-
sorfactorizationhastheadvantagethatthecovariancematricesaresmallbecause
thedimensionsofindividualmodesaresmallercomparedtothedimensionsof
the2Dmatrixarrangementandthat,asaresult,thetensorfactorizationcouldbe
computedfaster.Thisistrueifafullfactorizationisneeded,butinpractice,where
onlyarank-(R1,R2,...,RN)approximationisneededthereisnoadvantageof
computingthefullcovariancecomparedtousingamethodlikeOnline-SVDsince
computingthecovariancematrixforasinglemodencostsO(InkN=1Ik)al-
ready.Furthermore,thecoretensoralsoneedstobecomputed.Thiscorresponds
toprojectingthedataontoallorthogonalizedsubspaceswhereonesinglemode-n
productcostsO(kn=1RkkN=nIk).IntheALSalgorithmsuchmode-nproducts
havetobecalculatedN2timesperiteration!
Reconstructingasingleelementfromatensorrequiresevaluatingthefollow-

46

3.1.MATRIXFACTORIZATION

product:mode-ingnai1,i2,...,iN=Z×1uˆ1T,i1×2uˆ2T,i2...×NuˆNT,iN(3.4)
Zisgenerallyafulltensor,thereconstructionhascostsofO(n=1Rn)which
wherebyˆun,inisthein-throwvectorofmodematrixUn.SinceNthecoretensor
canbequitesignificant.Infact,comparedtoblock-wisefactorizationapproaches
thesecostsarealmostunacceptableinpracticalapplicationsaswillbeshownin
4.4.Section

3.1.5AlternativeMethods
Reviewingandcomparingtheplethoraofdifferentmatrixandtensorfactorization
techniqueswillbefarbeyondthescopeofthisthesis.Nevertheless,wewillat
leastpointatsomeimportantstreamsofresearchinmatrixfactorizationwhich
weconsiderareworthoffurtherresearchandinvestigationinthefieldofBTF
compression.

Non-NegativeMatrixFactorization
Thepresentedfactorizationtechniquesbynowareallbasedontheclassicalsin-
gularvaluedecompositionwhichguaranteesthebestrank-rapproximation(per-
block,per-mode)intheleast-squaressense.Anotherimportantmatrixfactoriza-
tionschemeisnon-negativematrixfactorization[LS00].Itcomputesafactor-
izationofanon-negativematrixVintonon-negativematrixfactorsWH.These
techniquesachievedsomeattentionaroundthebeginningofthisdecadewhen
graphicshardwarewasnotabletoprocessnegativevalues.Prominentexamples
aretheseparableapproximationsforarbitraryBRDFs[KM99]orthenon-negative
factorizationofsurfacelightfields[CBCG02].
Recently,thetechniquehadsomesortofcomebackintheformofavariant
calledconstraintfactorizationwhichallowstoenforcenotonlynon-negativity
butalsoothergeneralconstraintslikesparsityandevendomain-specificcon-
straintslikeenergyconservationiftherespectivefactorissupposedtobehave
likeaBRDF.Thiswayfactorscanbecomputedwhichareespeciallyusefulfor
non-parametriceditingasdemonstratedin[LBAD+06].
Sincenon-negativefactorsarenotanecessityfortodaysgraphicshardware
andtheenforcementofconstraintsusuallydecreasesapproximationqualitywe
willnotcovertheapplicationofthesetechniqueforBTFcompressionhere.How-
ever,itmightbeinterestingforfutureworktoinvestigatefactorizationtechniques
basedonperceptuallymoremeaningfulerrormetricsthanthestandardL2-norm.
47

CHAPTER3.BACKGROUND

actorizationFMatrixChainedIn[SvBLD03]Suykensetal.proposedtofactorizetheper-texelreectancefunc-
tionsofBTFsusingachainoffactorizations.Theideahereistofactorizethedata
indifferentparameterizations,whereaseachfactorizationismeanttorepresent
specificfeaturesfavoredbytheparticularparameterization.Themainmotiva-
tionoftheapproachwasthat,e.g.thehalfangleBRDFparameterization[Rus98]
allowstotransformthediagonalfeaturesresultingfromthespecularlobeinto
verticalfeatureswhichcanbefactorizedmoreefficiently.Generalizingthisap-
proachtothefullBTFtransportmatrixwouldbealsoaninterestingvenuefor
research.future

actorizationFchicalHierarAsalreadymentionedintheintroductionofthisthesisanimportantpropertyof
texturesandappearancemeasurementsingeneralisthattheycontainrelevant
featuresonvariousscales.Atextile,forexample,mightconsistofarepeating
colorpatternonalargescalecausedbydifferentlycoloredthreadsbutthereis
alsotheweavingpatternofthethreadsthemselvesonasmallerscaleetc.The
importantconsequenceforcompressionisthatthelargescalepatternsshould
notbestoredwiththesameresolutionasthesmallerscalepatterns.Thisprin-
cipleofscale-dependenceliesbehindmulti-resolutionapproacheslikehierarchi-
calwaveletbases.Inordertoexploitthemulti-scalestructureofdatainmatrix
factorizationthereareprincipallytwodifferentapproaches.
Thefirstapproachistotransformthedataintodifferentfrequencybandswhich
arethenfactorizedindependently.Laplacianpyramidshavebeenusedintheliter-
ature[MCT+05]butwavelettransformscanbeusedinthesameway.Theother
approachistousehierarchicalblockmatrixschemeslikeH-matrices[Hac99].
Herethematrixisrecursivelysubdividedintoblocksandeachblockisapproxi-
matedusingalow-rankfactorizationwhereastherecursionstopswhentherecon-
structionerrorliesbelowagiventhreshold.Thisschemecanbeeasilygeneralized
totensorsandhasbeenappliedtoreectancefieldsin[GTLL06].Avariantofthis
approachwhichkeepsandapproximatestheresidualmatrix/tensorblockoneach
levelhasbeenintroducedin[WXC+08].

Summary3.2Tosummarizethisbackgroundchapteraboutmatrixfactorizationwecollectedthe
mainpropertiesofthepresentedtechniquesinTable3.1.Theinsightsthatcanbe
gainedfromthistablearethefollowing:

48

3.2.SUMMARY

Block-wiseSVDevAdaptigularReTimemnrmnrbt(pn+pm)nmrb
Storage(m+n)r(mpn+npm)rb
econstructrrRbTwo-passTensorfactorization
Time(mn+nmbs)rbtNnNkn=1RkkN=nIk
Reconstructrbsn=1Rn
Storagemrb+(n+pmrb)snN=1InRNn+nN=1Rn
Table3.1:Ageneralcomparisonofthepresentedmatrix/tensorfactorization
schemesregardingtheirtimecomplexity,storagerequirementsafterrankreduc-
tion(notduringcomputation!)andreconstructioncostforasinglematrixelement.
AlltermsshouldbereadinO-notation.tdenotesthenumberofiterationsofthe
k-meansandALSmethodsrespectively(typicalvaluesare10≤t≤15).The
othervariablesareexplainedinthetext.

FactorizationComplexityFactorizationcostsareusuallylinearinthenumber
ofmatrixelementstimesthetruncatedrank.Formoresophisticatedtechniques
likeadaptiveblocksormulti-lineartensorfactorizationadditionalfactorslikethe
numberofiterations,thenumberofclustersorthenumberofmodesaffectthe
figures.

StorageReductionStoragerequirementsaregenerallyreducedtoasumofper-
ofmodeblocks.dimensionsHere,thetimesfinaladditionalperformancefactorsofalikemethodtheheatruncatedvilyrankdependsandonthethenumberper-
fmodeactorsorcanperbe-blockchosenfordimensionsagivenrespectierrorvelythreshold.andonItishoewloxpectedwthethatrankinwithincomparisonthese
toallowstandardtolowerSVDthemorerankelaboratesignificantly,methodsresultinglikeintensoranorimprovedblock-wisefcompressionactorizationratio
costs.reconstructioncheaperand/or

issuesinceReconstructionthetechniquesComplexityshouldbeReconstructionapplicableforcostperrenderingelementisapplications,animportantwhich
tionrequirescost,thealmostfrandomactorizationaccesstechniquesatbestpossiblepresentedspeed.herecanWithberespectroughlytodividedreconstruc-into

49

CHAPTER3.B

ACKGROUNDtwogroups.Ononeside,therearethemethodswhichrequireonlythecom-
putationofasingleinnerproductperreconstructedelement(standardSVDand
odsblock-wisewhichfrequireactorization).theOnreconstructiontheotherofanside,thereadditionalarethesubspacemoreortheelaborateevaluationmeth-
ofmode-nproducts(two-passandtensorfactorization).Thequestionthatneeds
tobeansweredis,iftheper-mode/subspacerankscanbechosensuchthattheir
productiscomparableinsizetotheper-blockrank.

50

CHAPTER4

FACTORIZINGTHEBTFTRANSPORTMATRIX

Inthepreviouschapterseveralgeneralmatrixfactorizationschemesaswellas
algorithmsfortheircomputationhavebeenintroduced.AccordingtoTable4.1
ereadyxceptbeenfortheappliedtwo-passtofBTFdataactorizationinthevariantsliterature.oftheInthismentionedchapterwetechniqueswillhacontribveal-ute
athoroughcomparisonbetweenthesemethodsexcepttwo-passfactorizationre-
gardingtheirpracticalapplicabilityintermsoffitting,storageandreconstruction
cost.TheoutcomeofthischapterwillbeatranslationofTable3.1intopractical
expressionsdependingonBTFsampleparameters.Thisrequiresspecifyingthe
arrangementofthe6-dimensionalBTFdataina2Dmatrixandgeneraltensor
andhowwewanttodealwithcolor.ThesetopicswillbediscussedinSections
4.1-4.3.InSection4.4wewillthenperformtheactualcomparisonintheformofsev-
xperiments.eempiricaleral

ArrangementDataMatrix4.1ThediscreteBTFrepresentationintroducedinEquation2.15canalreadybein-
terpretedasa2Dmatrixwith|K|rowsand|Id|columns.Eachrowisadiscrete
reectancefunctionofasinglepixelseenunderafixedviewdirectionforvarying
lightdirections.Since|K|isthenumberofpixelstimesthenumberofviewdi-
rectionsitusuallyholds|K||Id|(e.g.|K|=256×256×151and|Id|=151)
whichisnotquiteadequateforeffectivefactorization.Therefore,wewilltakea
closerlookattheindexsetsKandId.Idindexestheilluminationbasisandis
usuallygivenbyasetofllightdirections:
Id={(θi,0,φi,0),(θi,1,φi,1),...,(θi,l,φi,l)}
Kdescribesthediscretizationoftheoutgoinglight-fieldandisusuallygiven
bytheimageortexturesizeE=W×H={1,2,...,w}×{1,2,...,h}anda

51

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

SVDRegularBlock-wiseAdaptiveTwo-passTensor
[LHZ[KMBK03]+04][MPN[SvBLD03][SSK03]+02][MMK03]X[WWS[VT04]+05]

Table4.1:Matrix-andtensorfactorizationtechniquespublishedintheBTFcom-
literature.pression

setofvoutgoingdirectionsO={(θo,0,φo,0),(θo,1,φo,1),...,(θo,v,φo,v)}hence
K=E×O={(1,1,θo,0,φo,0),(1,1,θo,1,φo,1),...,(w,h,θo,v,φo,v)}.
NowK×Idcanbeinterpretedasasix-dimensionalsetofindicesandBcanbe
unrolledalongeachofthesedimensionswhichwillbeexploitedinthefollowing
sectionabouttensorfactorization.Forthepurposeof2Dmatrixfactorizationthe
usuallymostbalancedarrangementwillbetheonewhoserowsandcolumnsvary
bythespatialandangularindicesrespectively:
Bˆ:=BE×(O×Id)(4.1)
)x,y(ˆpledTheroperws-pixbelareBRDFscalled1.The4Drcolumnseectancebˆ(o,i)functionscanbeandcaninterpretedbeasinterpretedimagesasofsam-the
materialforonelightingandviewingdirection.
LetusnowtranslatethefiguresfromTable3.1intovaluesrelatedtoBˆ.We
dnownumberhaveofm=columns.|E|=Thew∙rahwassizetheofBˆnumberisofhencerowssizeand(Bˆn)==|wO∙×h∙Iv|∙l=.v∙lasthe
AccordingtothetablesontherightofFigures2.5and2.6valuesof81≤
v=l≤151aretypicalsamplingratesforthetheangulardomain.Inthespatial
domainwehaveusually64≤w=h≤512astypicaltexturesizes.Assuming
anumericalaccuracyof16bits(usingforexamplethehalfdatatype)thestorage
requirementsforBˆrangefrom2∙642∙812≈54MB2upto2∙5122∙1512≈11.95
GB.2812)≈rStandard∙21KBSVDandallo2rws∙to(5122+reduce1512)these≈r∙numbers570KB.tosomethingAccordingtobetween[KMBK03]2r∙(64we+
expectrtoliearound102–2∙102whichwouldresultin2-114MBofcompressed
storage.1theWstructureongetofal.aBRDF[WHON97]butcontainproposedtoneighborhoodcalltheseeffectsfunctions(masking,apparentshadoBRDFsws,becauseinterreectionstheyhaetc.)ve
that21violateMB=the106BRDFbytesprinciple.

52

4.2.TENSORDATAARRANGEMENT

Ifablockingschemewithpwhblocksalongthespatialdimensionandpvl
blocksalongtheangulardimensionisusedwehavetocalculatewithmemory
requirementsbetweenrbpwhpvl(pw8h+pv13l)KBandrbpwhpvl(pw524h+pv46l)KB.We
hopetoreducerbbyoneorderofmagnitudecomparedtorbutexpectthataround
50-100blocksmightberequired.Thenumberofblocksalongspatialandangu-
lardimensionshouldbechosendependingonthesamplingresolutionalongthe
dimensions.evrespectiUntilnow,onlymethodshavebeenpublishedwhichuseper-columnorper-
rowblocksexclusivelyasin[SSK03,MMK03]oraquitehighnumberofregular
blocks[MPN+02].Itcanbeexpectedthatgeneraladaptiveblockschemebased
onco-clusteringimprovesthisstateoftheart.

ArrangementDataensorT4.2TheBTFmeasurementindexsetW×H×O×Idgivesrisestoanatural4-thorder
tensorwhichconsistsofrow,column,outgoingandincomingdirectionmodes:
Bˆ:=BW×H×O×Id∈R|W|×|H|×|O|×|Id|(4.2)
Thisarrangementhasbeenproposedin[WWS+05].Theyarguedthatusingmore
BTF)modesfor(athe6-th2Dorderspacestensorofin-seemsandtooutgoingbethemostdirectionsnaturalisnotarrangementappropriateforsincethethere6D
aretoofewsamplesalongthemodesofelevationandazimuthalangle.Indeed,
ourtestsamplesconsistofonly81-151samplesforthewhole2Dspacesofin-
andmodesasoutgoingitwasdirections.proposedOnbythe[VT04]otherinhandorderitistoalsoreducepossiblerun-timetouselessreconstructionthenfour
cost:Bˆ:=BE×O×Id∈R|E|×|O|×|Id|(4.3)
ThisparticulararrangementisalsoknownasTensor-Textures.
Ofcourse,asabovetherawsizeofthetensorisBˆ=w∙h∙v∙l.Theexpected
compressionratioisquitemoredifficulttojudgewithoutexperimentsbecause
acustomrankcanbechosenforeachmode.Indeed,withthechosenrangeof
samplingrateswehavestoragerequirementsfrom2∙(64∙Rw+64∙Rh+81∙Rv+81∙
Rl+RwRhRvRl)bytesupto2∙(512∙Rw+512∙Rh+151∙Rv+151∙Rl+RwRhRvRl)
bytes.R,RIntheirbetweenoriginal20andpaper30.WongThisetwal.ouldhavleadetochosenstorageRw=w/2requirements,Rh=fromh/2819and
lvKBupto118MBforthecoretensoralonewhichiscomparabletothestandard
SVDconstructioncase.costUnfortunatelywould,beinsignificantlycomparisontohighertheinmatrixthisbasedcase.Alternatiapproachesvelythe,there-

53

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

spatialdimensioncouldalreadybereconstructedinapreprocesswhichwould
leadtotheTensorTexturerepresentationBˆ.Thereconstructioncostthenwould
becomparabletothestandardSVDcasewiththeonlydifferencethata"strategic
dimensionalityreduction"[VT04,p.4]becomespossiblewhichallowstoweight
theimportanceofviewandlightingvariation.Themotivationisthatareconstruc-
thantionawhichSVDpreservreconstructionesmoreevvenarianceifitsinRMSthevieerrorwismodehighercan.beperceptuallybetter

ColorwithDealing4.3UptonowwehaveneglectedthespectraldependencyofthediscreteBTFrepre-
sentation.Inpractice,measurementsoflighttransportareperformedforasetΛ
ofrequiredcolorforchannelseachλor∈Λ.spectralHencebandstheλindewhichxsetformeansevaerycompletesinglemeasBTFurementmatrixBˆpixλelis
dwillstandardbeΛ×RGBE×colorO×I.representationSinceourwetesthavcaseeΛ=BTFs{λrha,λvge,λbbeen}.Onemeasuredoftheusingsimplestthe
solutionsw3ouldbetounrollthisadditionaldimensionintotherowsorcolumnsof
:matrixtheBˆΛ:=[bˆ1,λrbˆ1,λgbˆ1,λb...bˆ|E|,λrbˆ|E|,λgbˆ|E|,λb](4.4)
Nowcorrelationtherowsbetweenofthisthedifmatrixferentcontaincolorrgbbandsis-reectancenotexploitedfunctions.optimallyThis.way,Alterna-the
tivelytechniques,wecouldhere.Foralreadyexampleanticipatethecolorthebandspresentedcouldmorebeinterpretedsophisticatedasfanactorizationadditional
modeintensorfactorization.Nevertheless,thisseemsabitlikeusingasledge-
nothammeramenabletocracktoaranknutreduction.becausethereTherefore,areusuallyouronlyapproachthreewillcolorbebandssimplytowhichapplyare
ade-correlatingtransformTC:R|Λ|→R|Λ|toeachcolortriple(bλr,bλg,bλb):
(bc0,bc1,bc2)T=TC(bλr,bλg,bλb)T
WeprefertousePCAasproposedin[HB95]inordertofindasuitable(affine-
canlinear)beTCusedbutasalternatiproposedvinelyalso[GMSK08].non-linearcolor-spacetransformslikeCIELab
ˆandfAfterwactorizeards,eachwematrixassembletheindependentlyBTF,matricesi.e.weBciapplyperasimpletransformedblockcolorschemebandonci
toplationofthebetweenactualfcolorbandsactorization.mostofSincethemostenergymaterialsconcenshotrateswaingreatoneordealtwofoofcorre-the
transformedcolorchannelswhichallowstocompressthelessimportantchannels
3Weusedherethewell-knownMatlabcnotationforconcatenatingcolumnvectorstoamatrix
54

4.4.EMPIRICALCOMPARISON

−much1moreaggressively(cf.Figure4.2).Forrendering,theinversetransform
TChastobeapplied.
bealIfwnotaysappliedindicatedpersingleotherwise,colorinthechannelfollowingmatrixtheBˆcfioractorizationtensorBˆci.algorithmswill

ComparisonEmpirical4.4

PLASTER

d||OW××IH||81x81256x256
RaBZipw8342,58MBGB

THERLEA

81x81256x256GB2,58MB881

PLASTIC

151x151128x124GB2,17GB1,48

CUSHION

151x151120x129GB2,18GB1,26

alsFigureare4.1:storedThewithset16-bitofmaterialsprecisionusedperincolorthe-channel.comparatiSincevethestudy.ThePLASTERmateri-and
LEApressionTHERusingmaterialsthehaveBZip-algorithmbeenacquiredreduceswithstorage12-bitprecisionrequirementsonly,alreadyentropbyy60%.com-

WhileTable3.1alreadygivesthemainpropertiesofthereviewedfactorization
techniquestheirpracticalperformancemainlydependsontheselectionofthevar-
iousrankparameters,astherearematrixrankr,per-blockrankrbandper-mode
rankRn,andtherowandcolumnpartitioningparameterspmandpn.Therefore,
inthissectionthevarioustechniqueswillbeappliedtoafewrealworldBTF
samplesinordertogetanotionhowtheseparametershavetobechosenforsatis-
fyingresultsinpractice.ThefourdifferentBTFsofvaryingcomplexityusedhere
aredepictedinFigure4.1.Thefirsttwomaterials(PLASTER,LEATHER)were
capturedwiththegonioreectometer-likesetupfromtheUniversityofBonn(see
55

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

Section2.6.3).Theothermaterials(PLASTIC,CUSHION)weremeasuredwith
themulti-cameradomealsofromBonn.
Eachofthesampleswillbecompressedwiththefollowingmatrixfactoriza-
techniques:tionactorizationfSVD/global••fixedandadaptiveblock-wisefactorizationwithoneandtwo-wayclustering
•tensorfactorizationwithfourmodes(imagerows,imagecolumns,view
direction,lightdirection)usingtheTuckerALSalgorithm
Eachtechniqueisappliedwithdifferentparameterssuchthatapracticalrange
ofcompressionratiosiscovered.Alldatavalueswillbestoredashalfprecision
16-bitoatsaccordingtotheproposedrevisedversionoftheIEEE754standard.
Differentquantizationtechniquescouldbeusedherebutsuchaninvestigation
wouldbeoutofthescopeofthisthesis.Reconstructionerrorandcostarecom-
putedforeachparametersetasfollows:
Theaverageroot-mean-squareerrorperreectancefunction
nmnmeRMS(A,A˜)=1|aij−a˜ij|2
jiiscomputedandthenplottedagainstthecompressionratio.Moresophisticateder-
rormetricsmightbeusedinfutureexperimentsbutfromourexperiencetheRMS
errorisstillagoodcompromiseofexpressivityandcomputationalcomplexity.
Thereconstructioncostforeachtechniqueandeachparametersetiscomputed
empiricallybyrenderinganimageofasimpleobjectcoveredwiththeBTFsev-
eraltimesusingasimplepath-tracer4andalsoplottedagainstthecompression
ratio.BothcurvescouldusuallyeasilybeidentifiedintheplotssincetheRMSE
increasesfromlefttorightwhilethereconstructioncostdecreases.Weplotthe
renderingtimesubtractedbythetimerequiredforrenderingthesamescenewith-
outanyshadingcalculations.Thiswayamorepracticalstatementcanbemade
comparedtothesimpleformulasforthereconstructioncostshowninTable3.1.
Apartfromthemerecostofreconstructingthediscretematrixelementsthereal
reconstructioncostscontainalsotheadditionalcostsforinterpolationandcolor
reconstructionandareinuencedbydifficulttoestimatebutsignificantfactors
.localitymemoryelik4enThevironmentpath-tracermapsandhashasbeenbeenwrittenusedintoC++renderbythemostofauthortheofimagesthisinthesis.thisItwork.supportslightingwith

56

4.4.EMPIRICALCOMPARISON

AllcomputationswereperformedonastandardPCsystemwitha2.4GHz
Intel(R)Core(TM)2CPUand4GBRAM.Allalgorithmshavebeenimple-
mentedbothinC++andinMATLABc5.FortheC++versionweexploitedthe
ublas6andCLAPACK7packagesforlinearalgebracomputationswithoutmulti-
threading,i.e.onlyasinglecorewasused.

SVDStandard4.4.1AssuggestedinSection4.3weapplySVDtothedecorrelatedcolorchannelsBˆci
independently:ˆBci≈TciSciBcTi(4.5)
HereTci∈R|E|×riisthematrixofper-channelEigen-texturesandBci∈R|O×Id|×ri
isthematrixofper-channelEigen-reectancefunctions.

imeTComputationAsalreadymentionedinChapter3weusedEM-PCA[Row98]whosecomplexity
inalscalespaperlinearlyproposeswiththetwodifnumberferentofmatriximplementationsentriesandofthethedesiredalgorithm:rank.anThein-coreorig-
vlineersionversionwhichsuitablerequiresfortoholdout-of-corethewholecomputationsdatamatrixwhichinmainprocessesmemoryonlyandaansingleon-
columnItatturnedatimeoutandthatinthuspracticeneedstotheholdin-coreonlyvtheersioneigenspaceoftheinalgorithmmemory.shouldbe
SampreferredRoweissinceitoriginalismuchfimplementationasterduethetobetteronlinevmemoryersionislocalityabout.40Inftimesact,slousingwer
tothanftheactorizein-coreourtestversiBTFson.withUsingathechosen64-BitreducedversionrankofofrMA=TLAB,256whichcompletelyalloin-ws
corecore,thefalgorithmactorizationrequiredtookaboutabout1420hours.minutesWeionourmplementedtestmachinealsoanwhileoptimizedtheout-of-C++
v50ersionpercentofthewhichonlinesuggestsalgorithmthatbtheutitin-corereducedalgorithmcomputationshouldtimesbeusedonlybywheneaboutver
possible.

ementsRequirStorageGivenatargetedcompressionratiotheper-channelrankriissimplydetermined
bysortingthesetofallper-channelssingularvalues{σci,j}accordingtotheir
5MATLABversion7.4.0.(2007a)Natick,Massachusetts:TheMathWorksInc.,2007
6http://www.boost.org7http://www.netlib.org/clapack/

57

PLASTER

PLASTIC

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

THERLEA

CUSHION

Figure4.2:RMSEandreconstructioncost(inseconds,dash-dottedlines)ofstan-
dardSVDforagivencompressionratio(greenstandsforper-channelfactoriza-
tionandreconstructionredforcostthedecreasesunrolledfrommatrix).lefttorightGenerally,whichthehelpsRMSEidentifyingincreasesthewhilecurves.the
FactorizingBˆΛrequireslessstoragepercomponentbutmorecomponentsare
neededtoachieveaRMSEsimilartothedecorrelatedper-channelfactorization.
Per-channelfactorizationwithoutcolordecorrelationisinefficient.

58

.4.4

EMPIRICAL

4.3:Figure(fromtotop

C

OMAPRISONbottom).RenderingsThefrombottomstandardrowshoSVDws

59

compressionreferencethe

for=rimages.

,10

,20

,40

80

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

magnitudeandincreasingthecorrespondingchannelrankstartingfromthebiggest
singularvalueuntilthestoragebudgetisreached.Thebenefitgainedfromde-
correlatingcolorchannelscanbeeasilyseenbycomparingagainstfactorizingthe
originalcolorchannelmatricesBˆλr,λg,λbandthecompletelyunrolled2D-matrix
BˆΛasillustratedinFigure4.2.
ityofIntheorderrtogeteconstructionanweimpressionrenderedwhatathesphereRMScoerrorveredtellswithabouteachthevisualmaterialqual-for
truncatedranksofr=10,20,40,80.Thecorrespondingcompressionratiosare
markedinthediagramsinFigure4.2.Itcanbenotedthatforthesimplermaterials
likestructionPLASTERwhichandcorrespondsPLASTICtoalreadycompression20componentsratiosofdeli1:300veraor1:477satisfying(≈8recon-and
4.5MB)respectively.TheLEATHERmaterialrequiresatleast40components
(1:120,(1:150,1816MB)MB)stillwhileshoforwssomeCUSHIONvisibleevendiftheferencesreconstructiontothewithreference80image.components

CostReconstructionThereconstructioncostscalesroughlylinearlywiththestoredrank.Forr=10
theandforpurer=80reconstructionabout10costseconds.are2.5seconds,forr=40theyarearound5seconds

SVDBlock-wise4.4.2Factorizingcolorchannelsindependentlyalreadycorrespondstoasimpleregular
blockscheme.Improvementsintermsofcompressionratioandreconstruction
costwerepossiblebecauseade-correlatingtransformwasappliedwhichreduced
thevarianceoftheapproximatingmatricesandintroducedonlyaminoroverhead
duringreconstruction.NowthequestionarisesifBTFfactorizationbenefitsina
similarwayfrommoresophisticatedblockschemes.AccordingtoSection3.1.2
wecanchoosetopartitiontherowspaceofBˆwhichcorrespondstotheBTFs
angulardomainorthecolumnspacewhichmeanstopartitionthespatialdomain
orbothofthemsimultaneously.Inallthesescasestheblockscanbechosento
beregularorgeneraltensorproductblocksadaptedtothedatausingaclustering
PCA.localelikalgorithm

imeTComputationAnadvantageofblock-wiseSVDisthatthematrixblocksusuallyfitintomain
memorywhichmeansthatnoout-of-coremanagementdespitetheassemblyof
blocksisrequiredandthein-coreversionofEM-PCAcanbeused.Furthermore,
factorizationcostsarelinearinrbandusuallyrb<r.Forexample,weused

60

4.4.EMPIRICALCOMPARISON

rtheb=48globalasfmaximactorization.umperAs-blockaresultranktheinourecompletexperimentsblock-wisecomparedftoactorizationr=256ofourfor
testdataUsingmatricesadaptivetakespartitioningonlyaboutwiththreesimpletofourk-meansminutesper(L2-error)material.requirestwoto
threeminutesperiteration(clusterassignmentandmeancomputation)whichre-
thesultsinaboutreconstruction30minuteserrorastotalclusteringcomputationmetrictimeif(local-PCA)teniterationsrequiresaretofused.actorizeUsingthe
todatabeinmultipleachiediterationbythewhichnumbermeansoftheiterations.fullfactorizationFurthermore,timeev(≈aluating3theminutes)recon-has
eachstructiondataverrorectorclusterhastobemetricisprojectedmoreeintoxpensieachveclustercomparedsubspace.tosimpleFortunatelyk-means,fromsince
ourexperienceafteraboutfiveiterationstheimprovementinreconstructionerror
isnegligiblewhichmeansthatweendupwithcomputationtimesaroundonehour
permaterialwhichisonlythreetimesslowerthanperformingaglobalfactoriza-
ationsubsetoftheofthewholedatamatrix.(aboutThese30-50%costscancanbebeusedusuallywithoutreducedsignificantlyfurtherbyafusingfectingonlythe
step.clusteringtheduringresults)

ementsRequirStorageChoosinganappropriatenumberofblocksisaninterestingquestionanddifficult
toanswerinpractice.Therefore,wemakeapragmaticdecisionhereandcreate
thefollowingtestcaseswhichwillbeperformedwithregularandadaptiveblocks:
1.Spatialpartitionusingpm=30partitions
2.Angularpartitionusingpn=30partitions
3.Spatialandangularpartitionsuchthattheresultingmatrixblocksareap-
quadratic.proximatelyCase1correspondstotheLocal-PCAcompression(adaptivespatialclustering
usingthereconstructionasclustererrormetric)wepublishedin[MMK03]and
itisespeciallysuitedforspatiallylargeBTFswithasparseangularsampling
becausethestoragerequirementsaredominatedbythenumberofpartitionstimes
thenumberofangularsamples.Case2isavariantofSattleretal.[SSK03]where
afixednumberofpartitionsequalingthenumberofsampledviewdirectionswas
used.Sincethestoragerequirementsarethendominatedbythenumberofview
directionstimesthespatialextentoftheBTFthismethodisonlypracticalfor
smallBTFswithasparsesamplingofviews.Thelastcasecombinesthetwo
andtherebyallowstoadaptthesizeofmatrixblockstothespatialandangular
rates.sampling

61

PLASTER

PLASTIC

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

THERLEA

CUSHION

forFigureagiv4.4:enRMSEcompressionandrratio.econstructionUsingcostgeneralofblocks,adaptivei.e.block-wisepartitioningfbothactorizationrows
andformancecolumnsofstandardperformsSVDbestbandutwithcomesclosesignificantlytothereducedcompressionreconstructionratio/RMSEcost.per-

62

4.4.EMPIRICALC

OMAPRISONPLASTIC

reblock-wiseRMSE=0.0318/12,gular

block-wiseadaptive8/12,RMSE=0.023

Figure4.5:ComparingregularblockswithadaptiveblocksusingL2-normand
reconstructionerrorasclustererrormetric.TheL2metricperformssurprisingly
badforcolumn2clustering(topright).Forrowclusteringthereisalmostnodiffer-
roencewsandbetweencolumnstheLbenefits-normandfromtheusingthereconstructionreconstructionerror(toperrorleft).asclusterCo-clusteringmetric.of
blocksBottomforrorw:b=the6isvisualclearlydifnotableferenceasbetweenblurredrehighlightsgular(left)intheandleftadaptiimage.ve(right)

63

cRMSE=1=:0.993024

cRMSE=1=:0.168015

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

cRMSE=1=:0.993026

cRMSE=1=:0.168017

cRMSE=1=:0.953033

cRMSE=1=:0.109021

cRMSE=1=:0.953047

cRMSE=1=:0.109038

c=1:1c=1:1c=1:1c=1:1
RMSE=0RMSE=0RMSE=0RMSE=0
Figure4.6:Comparingglobal(firstrow)andblock-wisefactorizationusingadap-
tivepartitioningofbothrowsandcolumns(secondrow)withsimilarreconstruc-
tioncosts.Wehavechosenrankr,rb=6forthethePLASTERandLEATHER
materialsandr=10,rb=9forthePLASTICandCUSHIONmaterials.Theim-
provementinreconstructionqualityforthesame(empirical)reconstructioncost
ismostvisibleforthecomplexmaterialsLEATHER,PLASTICandCUSHION.
Thebottomrowshowsreferenceimages.

64

4.4.EMPIRICALCOMPARISON

Figure4.4showstheexperimentalresultsofthethreetestcasesforeachofthe
testmaterialsusingadaptiveblockswiththereconstructionerrorasclustererror
metric.Itcanbeseenthatespeciallyinthecaseofathinmatrixwithunevenrow
andcolumndimensions(e.g.thePLASTERandLEATHERmaterialsconsistof
m=65536rowsandn=6561columns)itisquiteinefficienttopartitiononly
alongthesmallerdimension.Infactforalmostallinspectedcompressionratios
simultaneouspartitioningofbothrowsandcolumnsperformsbestintermsof
RMSE.Forcompressionratiosaround1:100thetwo-waypartitioningevencomes
closetothestandardSVDbutwithalmostonlyonethirdofthereconstruction
cost.

requiresRegularvs.significantAdaptiveBlockscomputationalAscostsmentionedduringabothevefitttheingusestageofsinceadaptivtheewholeblocks
todatausinghastoonlyberefgularactorizedblocksduringoronlyeachtheiteratL2ion.-norm?Isitworththeeffortincomparison
Figure4.5showsthetestresultsforthePLASTICmaterial.Theresultsforthe
ingotherresultsmaterialsinweresignificantqualitatiimprovvelyementssimilarfor.Itrocanwbepartitioning,observedi.e.thatspatialadaptiveclusteringcluster-
ofterestinglyreectance,thisisfunctions.notthecaseTheseforimprocolumnvementsarepartitioningalsowhivisuallychcorrespondssignificant.toIn-the
clusteringofimages.Here,clusteringbasedonthereconstructionerror(local
PCA)creasesimprotheverroresthequiteerroronlysignificantlymarginallycomparedandtosimplejustk-meansusingregularclusteringblockseven(topin-
2rorrightplotmetric.inTheseFigure4.5).resultsInsthisuggestcasethethefolloLwingnormispracticalobviouslyapproachnotawhichsuitableofferser-
thepartitioningbestcompromiseusingsimplebetweenk-meansandreconstructionregularqualitycolumnandblocks.fittingcost:adaptiverow

CostReconstructionAsbeforeFigure4.4showsthatthereconstructioncostsscaleroughlylinearly
withthestoredrank.Ifthepointsofsimilarrankfromthedifferentblockschemes
areconnectedanalmostperfectlyhorizontallineisobtained.Inourexamplefor
r=16itisc≈4sandforr=6wehavec≈2.3swhichmeanstheeffectof
improvedcachelocalityduetoasmallermemoryfootprintisnotquitesignificant
here.Nevertheless,ascanbeenseeninFigure4.5theregularblockschemesare
alwaysslightlyfasterthantheadaptiveblockschemes.Thereasonisthatthe
adaptiveblockschemesincreasetheprobabilityofadjacentrowsandcolumnsto
lieindifferentblockswhichinturnincreasesthenumberofblockchangesduring
rendering.Apparently,suchablockchangeusuallyimpliesabighopinmemory
whichisnotdesirableintermsofcachelocality.Thiseffectmightbecomeeven

65

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

morecachemissessignificantandfortheavmodernailablehighlymemoryparallelizedbandwidthGPUsthanwhichgeneralaremorepurposesensibleCPUs.to

actorizationFensorT4.4.3CostsComputationAssuggestedin[WWS+05]weusedtheTucker-ALSalgorithm[LMV00]for
computingthetensorfactorization.SinceaccordingtoSection4.2thereareN=
4modesweneedtofactorizethecompletedatafourtimesperiteration.For
eachconsecutifvelyactorizationwhichweneeddominatestotheprojectruntimethedatacostontooftheeachofmethodthesinceotherforthreeourmodesdata-
setsmaterials)theandmaximumthefper-modeactorizationofdimensiontheais256ttened(fortheprojectedPLASTERtensorcanandLEAusuallyTHERbe
performedin-core.Themostcostlyprojectionistheoneontothefirstmode
whichrequiresO(Ii0Ri0Ii1Ii2Ii3)operationswhichequalsO(mnRi0).Therun-
timedecreasesforeachconsecutivemodebut,e.g.thesecondmodestillrequires
Oally(RiR0Ri1=Ii11IIi2Ii3(the)imageoperationsrowwhichandiscolumnstillranksignificantischosensinceasinhalfourethexampixpleselreso-usu-
lution).i02Therefore,i0theworkloadofthetensorfactorizationisroughlyatleastsix
timeshigherthanthefactorizationofthecorrespondingmatrixusing,e.g.EM-
thePCAMAassumingTLABthattensoratoolboxcomparablebyBadernumberetal.of[BK07]iterationsforisoureused.Wxperimentseemplowhichyed
thoughts.theoreticaltheseconfirmedInourexperimentstheALSalgorithmconvergedusuallyafterabout10-15it-
toerationsthecomplewhichxisthememoryaboutaccesssameofpatternsnumberwhichiterationsoccurwhilerequiredforprojectingEM-PCA.ontoDuethe
difratherferentfactormodesoftentheinexpectedpracticefactorwhichofsixcorrespondscomparedtotocomputationEM-PCAturnedtimesoutoftoaboutbe
threehoursforourtestmaterials.Duringourexperimentswealsoimplemented
theTuckerALSalgorithmourselvesinC++andwediscoveredthatanoptimiza-
tionperformedformemorynearly15localitytimesiseslowerxtremelythantheimportantMATLABsinceourimplementation.unoptimizedC++code

ementsRequirStorageThemainmotivationbehindtheuseofTensorFactorizationisthehopethatre-
dundanciesnotrepresentedbythestandardco-variancematrixcouldbeexploited
toachieveimprovedcompressionratios.InthecaseofBTFcompressionthis
correspondstocorrelatingnotonlytheimagesorthereectancefunctionsrespec-
tively,butalsotherowsandcolumnsoftheimagesandtheview-andandlight

66

4.4.EMPIRICALC

OMAPRISONPLASTER

PLASTIC

THERLEA

CUSHION

Figure4.7:RMSEoftensorfactorizationcomparedtostandardSVD.Weused
alwaysR0=0.5∙WandR1=0.5∙Hfortheimagerowandcolumnranks.
ThemaximumranksR2andR3fortheview-andlightdirectionmodeswhereset
to32forPLASTERandLEATHERandto48forPLASTICandCUSHION.We
didnotplotthereconstructioncostshere,becausetheyareaboutthreeordersof
magnitudehighercomparedtostandardmatrixfactorization.

67

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

variationofthereectancefunctions.Wecaninterpretthisapproachasawayto
detectadditionalredundanciespresentintheclassicalSVDbasis.Accordingto
Equation4.5thisbasisconsistsofEigen-texturesandEigen-reectance-functions
whichmightexhibitsignificantself-similarity.
Indeed,Wangetal.reportedin[WWS+05]animprovedcompressionratiofor
thesameRMSEcomparedtoSVDforsomeexperiments.Asintheiroriginalpa-
perwesettheimagerowandcolumnranksR0,R1tohalfoftheimageresolution
inourexperiments.Fortheview-andlightdirectionmodeswekeptamaxi-
mumof32(PLASTER,LEATHER)or48(PLASTIC,CUSHION)dimensions
respectivelyandalsoperformedastrategicdimensionalityreductionasproposed
byVasilescuetal.[VT04]whichmeansstoringadifferentnumberofdimensions
fortheview-andlightdirectionmodes.
TheresultsareplottedinFigure4.7andtheyshowthatwecouldconfirm
Wangsresultsonlypartly.Infact,exceptfortheCUSHIONmaterialtheRMSE
isalwayssignificantlyhigher.Thisisparticularevidentifthecorrelationbetween
imagerowsandcolumnsislowasinthecaseoftheLEATHERandPLASTER
materials.SincethePLASTICandCUSHIONmaterialsarespatiallymorestruc-
turedandcontainrepeatingelementsthemethodperformsbetterherebutstill
mostlyinferiorcomparedtostandardSVD.Thesefindingsarealsoconfirmed
bytherenderedimagesshowninFigure4.8.EspeciallyfortheLEATHERand
PLASTICmaterialsandinallcasesofviewmodereduction(smallR2)theinfe-
riorRMSEisexpressedbyvisuallysignificantartifactslikespatialblurringand
reections.incorrect

CostReconstructioningReconstructionrequiresthecostisreconstructionthemainofdrasinglewbackpixofelstensorwhichfinactorizationturnrequiresbecausetheevrenderalua--
NtionfromofmatrixEquationf3.4actorizationwhichhashasonlycomplecomplexityOxity(On(rR)n)or.OIn(rb)contrast,respectively.reconstructionInour
experimentsthesecostsrenderthemethodliterallyimpracticalsincewehave,
e.g.ample20the≤r≤CUSHION80formateSVDbrialut64requires≤R0R,10≤=12864,Rand1=3064≤,RR22,3=≤4848,.R3For=ex-30
4r=meaning80.InnRpractice,n=we5.e898.240xperiencedtoachieaboutvean2000-3000RMSEtimescomparablehighertorunningSVDtimeswith8
forcorrespondsrenderingtothetestreconstructionimageswithtimestensorinthefrangeactorizationofhoursshownincompaFigureredto4.8seconds!which
InwhichorderyieldstomaktheeTtheensorTerenderingxturefeasiblerepresentation.atallweThiswaypre-multipliedtherenderingtheimagetimesbasisare
8Forthisreasonwedidnotplotthereconstructioncostsintothediagrams

68

4.4.EMPIRICALCOMPARISON

PLASTER

r=20,c.ratio1:300

THERLEA

r1:150,40=

R0,1=128,R2,3=9R0,1=128,R2,3=13

PLASTIC

1:477,20=r

R0,1=64,R2,3=14

CUSHION

=r1:120,80

R0,1=64,R2,3=28

R0,1=128,R2=17,R3=5R0,1=128,R2=25,R3=7R0,1=64,R2=28,R3=7R0,1=64,R2=48,R3=16

R0,1=128,R2=5,R3=17R0,1=128,R2=7,R3=25R0,1=64,R2=7,R3=28R0,1=64,R2=16,R3=48
Figure4.8:ComparingstandardSVDandtensorfactorizationwithstrategicdi-
mensionalityreduction(differentvaluesforlight/viewmodesR2andR3)using
thesameper-materialcompressionratio.ForthePLASTERmaterialthedif-
ferencesarehardlynoticeable.FortheLEATHERandPLASTICmaterialsthe
higherRMSEoftensorfactorizationisvisuallysignificantespeciallyinthecase
ofreducedviewmode(R2)whichleadstospatialblurring.Keepingthesame
rankforviewandlightmodesperformsbesthere.FortheCUSHIONmaterial
theRMSEandvisualimpressionarecomparableinthecaseofreducedR3(light
mode).Pleasenotealsothesignificantdifferencesinrenderingtime(seetext).

69

CHAPTER4.FACTORIZINGTHEBTFTRANSPORTMATRIX

Block-wiseRMSESVDReg.Adapt.TF
FittingTime20-30m3-4m60-120m2-3h
PLASTER0.0178.7MB20.4MB10MB101MB
4s2.9s2.7s2.3h
17MB30MB23MB101MB
LEATHER0.0145.8s3.3s3.0s3.2h
4.7MB18MB6.8MB56MB
PLASTIC0.0273.7s2.8s2.3s3.6h
CUSHION0.03818.8MB27.2MB20MB35MB
9.3s3.3s3s4.5h

Table4.2:InformalversionofTable3.1basedontheempiricalexperimentsfrom
Section4.4.Thecomputationandreconstructiontimesaregiveninh=hours,
m=minutesors=secondsrespectively.AccordingtoSection4.4.1weselected
thefollowingreducedranksintheSVDcase:r=20forPLASTERandPLAS-
TIC,r=40forLEATHERandr=80forCUSHION.Fortheothertechniques
parametersyieldingacomparableRMSEwerechosen.

onlysloweddownbyafactorbetween4and8butthestoragerequirementsare
obviouslyincreasedbythesamefactor.
TheseresultssuggestthattensorfactorizationbasedontheTuckerdecompo-
sitioncanbeusefulonlyforoff-linestorageorifthewholetensororatleastlarge
slicesneedtobereconstructedatoncebecauseinthiscasethereconstructioncosts
oftheindividualmodesamortize.Anyway,itmightbeaninterestingvenuefor
futureresearchtofindtensordecompositionsmoreappropriateforrendering.

Summary4.5InthischapterweanalyzedtheperformanceofSVD-basedmatrixfactorization
techniquesforBTFcompression.AfterpresentingarrangementsoftheBTFmea-
surementdataasmatrixortensorweempiricallycomparedstand-aloneSVD
againstregularandadaptiveblockpartioningandtensorfactorization.Aspromised
intheintroductionofthischapterwepresentheretheempiricalversionofTable
3.1.Table4.2comparespracticalfittingcosts,storagerequirementsandrecon-
structioncostsforafixedRMSEpermaterial.ThechosenRMSEcorrespondsto
areasonablevisualqualityforstandardSVD.

70

4.5.SUMMARY

4.2isThethatadapticonclusionveweblock-wisecandrafwactorizatfromtionhisseemschaptertoanddeliverbeparticularlythebestfromTcompro-able
miseperformancebetweeniscomthepressiondeterminingratiofandactortherereconstructionisnoothercost.Inpossibilityanycase,thaniftoruntimeusea
block-wisefactorizationscheme.Block-wisefactorizationusingregularblocks
wcanouldbebeusefulmoreifeffastficientfittingfilteringtimesareandanrequired.improvedOthercacheadvantageslocalityofsincethisdatatechniquepoints
adjacentIfitisinabouttheBTFcompressionmatrixremainratiothenadjacentstandardintheSVDcompressedwillusuallyberepresentation.themethod
ofPleasechoicenote,tsincehatitifofonlyferstheusuallycompressionthebestratiocompressioncounts,additionalratioforeaxpensigivenveRMSE.coding
butstepsthenliketheinimagepossibilityoffcompressionastandmightrandombeaccessappliedtoreconstructioncompressthedirectlydatafromfurtherthe
compressedrepresentationwillusuallybelost.
ofInourcompressionexperimentsratioonlytensorforfoneactorizationmaterialwasable(CUSHION)tobeatwhichstandardessentiallySVDinmeansterms
thatwecouldnotconfirmtheresultsfrom[WWS+05].Thiscouldbeexplained
byonetheorfactmorethatofWtheangtensoretal.usedmodeswhichmaterialswaswithnotatheparticularycaseforhighourtestcorrelationsamples(ealongx-
ceptwhichisableCUSHION).toeWxploitithnocorrelationsdoubtintensorfhigh-dimensionalactorizationisandatasetsinterestingwhichcannottechniquebe
elarforxploitedBTFusingrenderingonlymatrixwhichfrequiresactorization.efficientNevertheless,reconstructionfortheBTFsmethodandinisparticu-clearly
notmodeswoptimal.asnotAshighoureenoughxperimentstohavsignificantlyeshownthereducethecorrelationRMSEalongcomparedthetoadditionalSVD
fortheplicabilitysameoftensorcompressionfactorizationratio.isEvtheenfactmorethatsevtheereinrandomtermsofaccessthepracticalreconstructionap-
ofslowsinglecomparedBTFpixtoelsmatrixwhichfisactorizationrequiredfortechniques.renderingTherefore,applicationstensorisfunacceptableactorization
seemssub-tensorstobeatmoreonceliksuitableetheforvisualapplicationsizationoftime-vrequiringaryingthemultivdecompressionariatevolumeofwholedata
asdemonstratedin[WXC+08].

71

C

HAPTER4

.

AF

72

CTORIZINGTHEB

T

F

T

RANSPORTM

TARIX

CHAPTER5

DATA-DRIVENLOCALCOORDINATESYSTEMS

InmatrixChapterf4actorization.wecomparedThesesevtechneraliquesBTFdonotecompressionxploitanyalgorithmspriorknosolelywledgebasedabouton
thewellknogeometrywnfactofthatthethecapturedeffectivenmaterial.essofThisimage-basedseemsabitofarepresentationswasteissinceitstronglyisa
relatedtotheaccuracyofthegeometrythereectiondataisparameterizedon
[GGSC96].Foractualexample,geometryinupthetoeallxtremevisiblecase,detailswhereandthecorrectbaselocalgeometrycoordinatecoincidessystemswithpa-the
thatrameterizingneedstobethestoredincomingistheand"pure"outgoinglightdirectionstransport,arei.e.givtheen,conthevonlyolutionoftheinformationsur-
faceBRDF(whichsubsumesthesmall,invisiblesurfacedetails)withtheincom-
inglightingplusinter-reections.Asshownbyrecentresultsthelighttransport
matrixisoflowrankinthiscase[MSRB07].
Unfortunately,inpracticeneitherthegeometryisknown,becausethiswould
requireanexactgeometryreconstructionwhichisdifficulttoobtainfromcom-
plexmaterials,northelocalcoordinatesystemsareknownbecauseincaseof
ananisotropicBRDFthiswouldrequireknowledgeofthemicro-geometry.The
resultingeffectsaretwofold:
1.Pisarallaxprojected-reectontoedthesameradiancelocationfromphoftheysicallybasedifferentgeometrysurfandacethuslocationstreated
withinthesamereectancefunction(∼samerowinBˆ).
2.MisalignedBRDF-thelocalcoordinatesystemwhichparameterizesin-
andoutgoingdirectionsisusuallyderivedfromthebasegeometry.There-
fore,theparameterizedBRDFmeasurementvectors(again:rowsinBˆ)
fromdifferentsurfacepointswillbedifferentevenforobjectswithuniform
5.1).Figure(seeBRDFticsBothlikefefectsco-vhamperariancethebecauseeffectithevyenessofintroducevcompressionariancetothetechniquesdatabasedmatrices.onstatis-The
73

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

Figure5.1:SmalldeviationsofthebasegeometryS(red)fromtherealsurface
O(green)leadtomisalignmentsinthereectancedata:theactuallymeasured
BRDFslice(bottom)isrotatedandchangesitsshapedependingonthesurface
slope.Asaresultthedataatthepointsxandxdiffersifputintothecommon
coordinatesystemderivedfromS(red)evenforidenticalsurfaceBRDF.

factorizationalgorithmsobviouslycannotdecideinthiscaseifthevarianceis
partoftheactualappearanceorjustresultingfromoneofthesetwoeffects.
Readersexperiencedinimage-basedrenderingareofcoursefamiliarwith
theseproblems.Infact,theseeffectsareinevitableinimage-basedrenderingbe-
causeexactgeometrywithscreen-pixelaccuracyandlocalframesalignedwith
theprincipalBRDFfeaturesarerequiredtoavoidthem.Apartfromthefactthat
suchanaccuratereconstructionofgeometryandBRDFfromimagesisdifficultto
acquireitalsocontradictstheoriginalmotivationofimage-basedrenderingwhich
wasindependencefromscenecomplexity.Thisisespeciallytrueinthecaseof
typicalBTFswiththeirsmallandfuzzygeometryandtheresultingcomplexlight
transport:themeso-scalegeometryofBTFsisusuallyquitehardtoreconstruct
andanexplicitrepresentationwithintherenderingsystemwouldbeveryexpen-
siveintermsofstorageandrendering.Therefore,inthischapterwepropose
anintermediateorhybridrepresentationresidingbetweenpuregeometricand
image-basedrepresentations.Looselyspeaking,themethodcanbeinterpretedas
anadaptionofnormalmappingtoBTFs.
Originally,normalmapping[Bli78]wasdesignedtosimulatetheshadingvari-
ationsresultingfromsmall-scalegeometry.Theideawastodiscardthesmall-
scalegeometryandtouseonlyitsnormalsintheshadingcomputation.Thereby,
normalmappingdoesnotrendercorrectmasking,shadowsandsilhouettesbutit

74

Figure5.2:Theprinciplebehindouralgorithmisthecomputationofconsistent
localframes(illustratedbythergb-encodednormalandtangentmaps)usinga
novelalignmentalgorithmandangularreectancereparameterizationaccording
totheselocalframes.Intheshownexample(PLASTICBTF)thedataisthen
compressedusingmatrixfactorizationtechniques.Forrenderingtheoriginaldata
isreconstructedbyapplyingtheinverseofthelocalframerotationmatrices.

createsareasonableillusionofmesoscopicsurfaceinthecaseofapproximately
aces.surfatWewillexploitnormalmapsinaslightlydifferentway:weperformanangu-
larreparameterizationofthemeasuredreectancedataaccordingtothemapof
localframesasillustratedinFigure5.2.Asmentionedabove,wewillnotonly
employnormalmapsforthatpurposebutfulllocalframesgiven,e.g.asper-texel
zyz-EuleranglesΦx=(φx,θx,ψx).ThenthereparameterizedBTFBV,Φisgiven
ws:folloasBV,Φ(ωi;x;ωo):=BV(RΦTx∙ωi;x;RΦTx∙ωo)
whereasRΦx=Rz(φx)∙Ry(θx)∙Rz(ψx)
istheper-texelrotationmatrixthatrepresentsthelocalframe.Thediscreteversion
ofBV,ΦcannowbecompressedusingmatrixfactorizationasexemplifiedinChap-
ter4.Weexpectthatthecompressionperformanceespeciallyofcorrelationbased
algorithmslikematrixfactorizationcanbeimprovedthiswaybecausevariance
resultingfromdeviationsbetweenrealnormalsandnormalsfromthereference
surface(cf.againFigure5.1)willbereducedeventhoughparallaxandmasking
effectsarenot−1corrected.Duringrendering,wesimplyneedtoapplytheinverse
rotationmatrixRΦxtothein-andoutgoingdirections.

75

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

Thequestionnowimmediatelyariseshowtheselocalframeswillbeobtained.
Astraight-forwardsolutioncouldconsistofastandardshape-from-shadingor
photometric-stereomethodwhichestimatesnormalsperdiscretesurfacepoint.
methodsUnfortunatelylike,[RsuchTG97]anassumeapproachdifwfuseouldbereectancequiteandlimited:theymostestimateaphotometricnormalmapstereo
foroneviewpointonly.Furthermore,theseapproachesestimateonlynormals
andnotafulllocalframewhichneglectstherotationaroundthenormalwhich
isingfullimportantlocalforframes,anisotropici.e.normalmaterialsand.tangentTherefore,vaectorno,velwillbealgorithmintroducedforincomput-the
following.Weprefertocallthismethodanalignmentalgorithmbecauseittries
tocomputelocalframeswhichmaximizethealignmentbetweentheper-texelre-
functions.ectanceInparticulartheapproachconsistsofthefollowingcontributions:
•aboutdata-drivenunderlyingestimationreectanceoflocalproperties,coordinatei.e.thesystemsmethodwithoutdoesanynotrelyassumptionsona
modelreectancespecific•sionimprovedalgorithmscompressionwithnegligibleperformanceadditionalofmatrixrun-timefactorizationcostbasedcompres-
•eablesxploitationextremelyofftheastSphericalcomputationHarmoniofcssphericalFourier-shiftcorrelationstheoremandmightwhichbeen-of
relevanceforapplicationsbeyondcompressionlike3Dtexturereconstruc-
tionTheremainderofthischapterwillbeorganizedasfollows.InSection5.1the
coreofouralgorithmisdevelopedformaterialswithnearlyuniformBRDF.Then
inSection5.2itisgeneralizedtoarbitrarymaterials.Resultsandexperimentsare
thetopicoftheclosingSection5.3.

5.1Localframealignmentforuniformmaterials
Thekeypointofthealgorithmistocastthecomputationoflocalframesasa
problemofpairwisealignmentofreectancefunctions.Inordertohighlightthe
differencesbetweenourmethodandstandardphotometricstereoletusfirstintro-
duceageneralphotometricstereoframework.
Instandardphotometricstereoangulardependentimagemeasurementsbx(ωi,ωo)
arecomparedagainstaBRDFmodelusingaquadraticerrorfunctionalpersurface
:xpointEx(α,Φ)=|bx(ωi,ωo)−fx(α,Φ;ωi,ωo)|2(5.1)
ωi∈Idωo∈O
76

5.1.UNIFORMLOCALFRAMEALIGNMENT

HereαisasetofBRDFmodelparametersandIdandOarethesetsofmea-
suredviewandlightdirectionsasinChapter4.Typically,onlyanormaldirection
(φ,θ)isestimatedinsteadofafulllocalframeΦ,onlyasingleviewpointisused
(|O|=1)andadiffuseBRDFisassumed.Inthiscase,thefunctionalExcanbe
minimizedbysolvingalinearsystemofequations.InthecaseofgeneralBRDF
modelstheBRDFparametersetαhastobeoptimized,too,whichusuallyrequires
anon-linearoptimizationwhichalternatesbetweennormalandBRDFparameter
[GCHS05]).(e.g.estimationThemainproblemofthisstandardapproachregardingtheimprovementof
BTFcompressionistheassumptionofaspecificBRDFmodel.Thisisinappro-
priateformaterialswithcomplexBRDFsorstrongmaskingandlighttransport
effects(inter-reections,subsurface-scattering).Onewaytorelievethiswouldbe
toallowacompletelygeneralreectancefunction:
Eˇx(a,Φ)=|bx(ωi,ωo)−a(Φ;ωi,ωo)|2(5.2)
ωi∈Idωo∈O
witha(Φ;ωi,ωo):=a(RT(Φ)ωi,RT(Φ)ωo)wheretherotationmatrixR(Φ)=
Rz(φ)∙Ry(θ)∙Rz(ψ)parameterizedbyzyz-EuleranglesΦ=(φ,θ,ψ)describes
frame.localtheOfcourse,inthisformtheerrorfunctionaldoesnotmakemuchsensesince
a=bxandΦ=0wouldbethetrivialsolution.Obviously,anotherconstraintis
required.WhilestandardphotometricstereoassumesaspecificBRDFmodelour
constraintistoassumeaspatiallyuniformBRDF(weshowinSection5.2how
thefunctionalcanbegeneralizedinordertodealwithmaterialswithnon-uniform
BRDFs,too).Thisresultsinthefollowingerrorfunctionalwhichintegratesover
thesurface:
E(a,Φ(∙))=|bx(ωi,ωo)−a(Φ(x);ωi,ωo)|2(5.3)
x∈Eωi∈Idωo∈O
ThisfunctionalcanbelocallyoptimizedusingforexampleanEM-stylealgo-
rithm(ExpectationMaximization),whichalternatesbetweentheestimationofa
reectancefunctionaandthespatiallyvaryingmapoflocalframesΦ(x)bymin-
imizingthefunctionalEˇx(a,Φ(x))whileleavingafixed(cf.Algorithm1).
Unfortunately,thisapproachwouldbequiteslowandpronetolocalminima.
Aglobalevaluationonadiscretegridofrotations{Φi}0<i<Gwouldalsobeinfea-
sible.Ifweassume,forexample,adesiredaccuracyofonedegreealongallthree
angulardimensionsEˇactuallyhastobeevaluatedfor360×90×360rotations.
Therefore,weproposetoreformulatetheobjectivefunctionasacorrelation:
C(a,Φ(∙))=bx(ωi,ωo)a(Φ(x);ωi,ωo)(5.4)
x∈Eωi∈Idωo∈O
77

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

Inordertounderstandwhatiswonbythissmallchangeletusnowassumethat
thereectancefunctionsarecontinuousanddefinedoverthewholespheresof
incomingandoutgoingdirectionsΩiandΩo.Thenwecaninterpretthecorrela-
tionbetweentwocontinuous4Dreectancefunctionsaandbasameasureof
alignment:Cx(Φ)=bx(ωi,ωo)a(Φ;ωi,ωo)dωodωi.(5.5)
ΩΩoiIfweassumethataandbxareonlyrotatedversionsofeachotherthenthiscorre-
lationwouldreachitsmaximumforthealigningrotation.Inotherwords,Cx(Φ)
representsthelikelihoodforthelocalframeΦtoaligntherotatedfunctions.Max-
imizingCx(Φ)nowcorrespondstothedeterminationoftheEuleranglesΦ¯which
maximizethecorrelationbetweenbxandtherotateda:
Φ¯=argΦmaxCx(Φ)(5.6)
ByemployingtheFourierTransforminthegroupofrotationsSO(3)thismaxi-
mizationcanbecomputedinfrequencyspacewhichisthekeytotheimproved
performanceofourmethod.Itisconvenientforthederivationofthissteptofirst
reducethecomplexityoftheproblemtothedomainof2Dreectionfunctionsde-
finedoverthesphere.Ageneralizationto4Dreectancefunctionswillbegiven
ards.afterw

elationcorrSpherical5.1.1Modifyingtheabovecorrelationterm5.5tooperateonfunctionsdefinedonthe
sphere(anddroppingthespatialindexforconvenience)leadstothefollowing
gral:inte

CaΩ,b(Φ)=b(ω)a(Φ;ω)dω(5.7)
ΩFThisourierinteshiftgralhastheoremtheisformofapplicableaspherical[KR03]convwhicholutiongeneralizessuchthatthethebasicFgeneralizedourier
shiftdeed,wetheoremcandefineddecomposefor1Dbandlimitedfunctionsatoandbfunctionswithdefinedmaximumoverthebandwidthsphere.LintoIn-
basis:(SH)HarmonicsSphericaltheLa(ω)=aˆlmYml(ω)
l=0|m|≤l
Lb(ω)=bˆlmYml(ω).
l=0|m|≤l
78

5.1.UNIFORMLOCALFRAMEALIGNMENT

ThegeneralizedFouriershifttheoremnowstemsfromthefactthatarotatedSH-
basisfunctioncanbewrittenasalinearcombinationofSH-basisfunctionsofthe
band:same

Yml(RT(Φ)ω)=Dklm(Φ)Ykl(ω)(5.8)
l|≤k|HereDklm(Φ)denotesaWigner-Dfunction.From(5.8)follows
Lb(RT(Φ)ω)=bˆlmDklm(Φ)Ykl(ω)(5.9)
l=0|k|≤l|m|≤l
whichbyexploitingtheorthogonalityoftheSHbasisimmediatelyleadsto
LCaΩ,b(Φ)=aˆklbˆlmDklm(Φ)(5.10)
l=0|k|≤l|m|≤l
SincesitionoftheCΩright(Φ)handinthesideofrotationEquationgroupS(5.10)O(3)hasthetheformgeneralizedoftheFFourierouriershiftdecompo-theo-
remfollowsa,bimmediatelybycomparingcoefficients:
cˆlmn=aˆlmbˆln(5.11)
whichnow(analogouslytoconvolutionsintheplanardomain)allowstocompute
Ωlathe(ω)Fandourierb(ωcoef)(infficientsact,cˆanmnouterofCa,bproduct(Φ)byhastobemultiplyingcomputedtheFperourierband).coefficientsof
ThedirectevaluationofEquation(5.10)hascomplexityO(L3).Fortunately,
thereEquationexists(5.10)an(inforvaerse)gridFastofF(2Lourier+1)T3ransformrotationswith(FFT)comple[KR03]xitywhichO(Le3vlog2aluatesL)
comparedtoO(L6)forthedirectevaluation.
evWealuationbyimplementedapplyingbothinvtheersedirectFFTevusingaluationtheoffreelyEquationavailable(5.10)andC-libraryitsefSOFTficient
(5.7)[SOF].usingFurtnumericalhermore,weintegration.implementedTablethe5.1"shobrute-force"wstimingevaluationresultsoffordifEquationferent
.ofaluesvL

4DtoGeneralization5.1.2Togeneralizetheresultsfromtheprevioussectiontothecorrelationof4Dre-
ectancefunctionsinEquation(5.5)wefollowatensorproductapproach,i.e.we
79

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

LEqn.(5.7)|Ω˜+|=151Eqn.(5.10)directEqn.(5.10)FFT
841.8730.32527.6730.6850.3360.029
5.326>100015.14416Table5.1:Averagecomputationtimes(inmilliseconds)forsphericalcorrelation
onanO(L3)gridforvaryingLonanAMDAthlon3200+.

representreectancefunctionsinthetensorproductbasisofSphericalHarmonics:
La(ωv,ωl)=aˆlm1l12m2Yml22(ωv)Yml11(ωl)
l1,l2m1,m2
leadsRepeatingtothethefollostepswingfromlengththeypresumvioussubsection(weomitthemhereforbrevity)
LCaΩ,b×Ω(Φ)=aˆl1ml12m2bˆlm1l12m2Dlm22m2(Φ)Dlm11m1(Φ)(5.12)
l1l2m1m1m2m2
pleAfterxityaO(Lsimple5)whichreorderingwouldofleavtermseusthewithdirectaneevxpensialuationveOof(L8this)sumalgorithm.hascom-Ap-
plying6the2inverseFFTinatensorproductfashionwillresultinastillexpensive
O(LlogL)algorithmandreturnsthecorrelationforarbitrarycombinationsof
Φ=rotationsΦ.(ΦW1e,Φ2)currently∈SOha(3)ve×notSO(3)foundawhilewaywetoerequirexploitonlythis.thoseelementswhere
21ment.FAnotherorL=8problemeachofthereectancetensorfunctionsproductconsistsrepresentationof4096isSHitscoefmemoryficientswhichrequire-
easilysumsuptohundredsofmegabytesofdatafortypicaldatasets.Therefore,
weproposetofactorizethereectancefunctionsa,bintoasumofproductsof
2Dcomplefunctionsxity.whichSpecifically,reduceswefindboththerepresentationsmemoryoftherequirementsformandcomputational
Ka(ωv,ωl)≈a1,i(ωv)a2,i(ωl)
iKb(ωv,ωl)≈b1,i(ωv)b2,i(ωl)
iusingmodifiedforexamplecorrelationSVD.termSubstitutingtheserepresentationsforaandbleadstoa
KKC˜aΩ,b×Ω(Φ)=CaΩ1,i,b1,j(Φ)CaΩ2,i,b2,j(Φ)(5.13)
ji80

5.1.UNIFORMLOCALFRAMEALIGNMENT

4LEqn.291.2(5.5)Eqn.26.86(5.12)Eqn.1.145(5.13)K=4K=62.591
168N.N.>1500N.N.>3500195.93710.683445.11823.803
Table5.2:Averagecomputationtimes(inmilliseconds)forcomputingthecor-
relationof4D-reectancefunctionsonanO(L3)gridforvaryingLonanAMD
Athlon3200+.DirectapproachesarenotfeasibleforL>4.

whichreducesthe4Dcorrelationtoasumofproductsof2Dcorrelations.Using
againtheinverseFFTforsphericalcorrelationswenowhaveanO(K2L3log2L)
algorithm.Inourexperimentsweset4≤K≤8buttypically4components
sufficewithoutdegradingtheresultssincethemainfeaturesrelevantforthealign-
mentarecapturedinthisrepresentation.
Asinthe2DcaseweimplementedthedirectevaluationofEquation(5.12)
andsimplenumericalintegrationforcomparison.Thehugeperformancebenefits
gainedfromEquation(5.13)areillustratedinTable5.2.UsingthesettingsL=8
andK=4wealignaboutonehundredreectancefunctionspersecondfora
sufficientlydensegridofrotations.

ogetherTitPutting5.1.3Nowtheingredientsrequiredtoformulatethemaximizationalgorithmforfunc-
tionalC(a,Φ(∙))canbeputtogether.Asalreadyindicatedthealgorithmwill
alternatebetweentheestimationofanalignmentfunctionaandtheestimationof
thelocalcoordinateframesΦ(x)whichemploysthecorrelationcomputationin
space.yfrequencGivenasetofreectancefunctions{bx}x∈Ewesimplycomputeaastheir
mean.Then,iteratively,eachbxisalignedtoausingthefactorizedcorrelation
equation(5.13).SinceusuallyL=8thediscretegridofrotationsisstillrela-
tivelysparse.Therefore,thestrategywillbetousethelocationofthefoundmaxi-
mumasinitializationforanadditionalnon-linearoptimizationstepusing,e.g.the
Levenberg-Marquardtalgorithm.ThesestepsaresummarizedinAlgorithm1
Giventhecomputationtimesforasinglealignmentthecomputationtimefor
awholeBTFwithanextentof2562texelsaddsupabouttoaboutonehourusing
fouriterationsinAlgorithm1andincludingthepreprocessingtimerequiredfor
factorization,SHprojectionandnon-linearoptimization.
81

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

Algorithm1Alignmentofreectancefunctions{bx}x∈E
0=j1:2:N=|E|
3:a0=bx0{choosex0∈Erandomly}
epeatr4:5:forx∈Edo
6:Φx=argmaxΦCaj,bx(Φ)
orfend7:8:aj+1(ωi,ωo)=N1x∈Ebx(Φx;ωi,ωo)
10:until<τ{istheincreaseinaccumulatedcorrelationx∈ECaj,bx(Φx)
9:j=j+1
iterations}otwbetween11:12:returnSetoflocalframes{Φx}

5.2Local-framealignmentformaterialswithnon-
BRDFsormunifMostobjectsaremadeofdifferentmaterialswhichmayvaryacrossthesur-
face.ApplyingtheapproachfromSection5.1willthenalignreectancefunc-
leadtionstowhichatleasthavebeensub-optimalmeasuredresults.fromOurprobablysolutionviserytodifapplyferentaBk-meansRDFswhichclusteringmay
algorithmnormalizedvwithersionanoftheorientationincorrelationvarianttermdistance(5.5):metric.Themetricisbasedona
d(a,b)=1−ΦmaxC¯a,b(Φ)(5.14)
d(a,b)definesaso-calledsemi-metric(triangleinequalitydoesnothold)andwe
useusingitasthisanmetricorientationareectanceinvariantfunctiondistancewillbemetricforassignedthetothek-meansclusterclustering.wheretheBy
correlationbetweentheclustercenterandthesuitablerotatedreectancefunction
maximized.is

ResultsandExperiments5.3Totestouralgorithmweappliedittosyntheticdata,measuredBTFsandafar-
offieldasurfsimpleaceplane.reectanceToevfield,aluatei.e.theaimproBTFvementparameterizedincompressionona3D-objectperformanceinsteadfor
themeasureddataglobalmatrixfactorization(seeChapter4)wasappliedtothe
alignment.afterandbeforedatasets82

5.3.EXPERIMENTSANDRESULTS

Figure5.3:Synthetictest:theoriginaldatamatrixBˆofthematerialshowninthe
loinswerintorighttheismatrixturnedimagesintoanaligneddemonstratedatahowmatrixwellBˆΦthexbyangularouralgorithm.featuresareThealignedzoom-
–thediagonalfeatureshavebeenturnedintoalmostperfectlyverticalfeatures.

DataSynthetic5.3.1Thebasicprincipleofthealgorithmwastestedbycreatingasyntheticdataset
fromaheightfield("noisy"Eurographicslogo),atangentmap(modulatedbyaco-
sine[AS00])function),withoutandacomputingsingleanisotropicinterreections.BRDFSincethis(Ashikhmin-ShirledatasethasynoBRDFregistra-model
tionerrorsandmeasurementnoise,varianceinthedatamatrixresultsonlyfrom
81parallax×81=and6561wrongdirectionslocalandcoordinateappliedsystems.theWalignmentesampledalgorithmthissyntheticdescribedBTFintheat
previoussection.UsingthreeiterationsandthesettingsL=8andK=5the
thealignmentangulartookfeaturesaboutoffivetheminutes.reectanceFigurefunctions5.3sho(rowswstheofBˆresults.)areNotealignedhowresult-well
inginadatamatrixwithalmostidenticalrows.Obviously,suchamatrixhasa
significantlylowerrankthantheoriginalmatrix.

Measur5.3.2BTFsedInordertotestthealgorithmalsowithrealworlddatacontainingregistration
errors,measurementnoiseandsignificantmaskingitwasappliedtothemeasured
BTFsfromFigure4.1.TheresultsareshowninFigures5.4and5.5.Theplots
showthatthereductioninRMSEisquitesignificantcomparedtostandardSVD.

83

PLASTER

PLASTIC

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

THERLEA

CUSHION

Figure5.4:RMSEandreconstructioncostofglobalfactorization(standardSVD)
fororiginaldataandafterreparameterizationtolocalframes.Forallmaterials
tested,theRMSEisreducedforthesamecompressionratioafterapplyingthe
alignment.Usually,computingthealignmentbetweenfull4Dreectancefunc-
tionsusingthefactorizedapproximationperformancebest.Theadditionalrecon-
structioncostfromlocalframerotationsisalmostnegligible.

84

5.3.EXPERIMENTSANDRESULTS

cratior=1:6994

1r:=59610

1r:=19075

r1:=95310

Figure5.5:Visualcomparisonofglobalfactorization(rank-rapproximation)
without(firstrow)andwith(secondrow)angularreparameterizationusingthe
localframescomputedbyouralignmentalgorithm.Spatialandangularblurisre-
ducedsignificantlyespeciallyforthehighcompressionratiosshown.Thebottom
rowshowsreferenceimages.

85

CHAPTER5.DATA-DRIVENLOCALCOORDINATESYSTEMS

Figureechinite.5.6:TheleftCompressingimageshoBTFwsdatatheresultmeasuredusingon3Dadaptivegeometry,block-wiseinthisfcaseaactorizationfossil
(prightn=the32,presultm=1after,rb=8alignment)withoutwithouralignmentmethodofislocalshown.coordinatesystems.Onthe

Inallcasesthealignmentofthefull4Dreectancefunctionsout-performsthe
useofonlyasinglefixedviewandreconstructioncostincreasesonlyslightly.
loThew-rankimprovedapproximationsRMSEresulastsshoalsownininanFigureimpro5.5.vedNevvisualertheless,qualitytheefespeciallyfectisfornot
asimpressiveastheplotssuggest.Onereasonforthismightbetheadditional
resamplingstepinvolvedinapplyingthelocalcoordinatesystemtransformation
actorization.fbefore

5.3.3MeasuredFar-FieldSurfaceReectanceField
AninterestingapplicationofourmethodisthecompressionofBTFdataparam-
eterizedona3Dsurfaceinsteadofaplane.Inthiscasethemeasuredreectance
dataisusuallyparameterizedbythelocalcoordinatesystemsofthemeshtrian-
gles.Sincethegeometryoftheproxygeometrymeshoftendeviatessignificantly
fromtherealgeometry,thedeviationsbetweenthereallocalcoordinatesystems
andtheonesderivedfromthebasegeometryareusuallyhigherthaninthecase
ofaplanarmaterialsample.Assketchedintheintroductionofthischapterthis
meansincreasedvarianceorequivalentlyincreasedrankofthelighttransportma-
trix.Todemonstratetheeffectivenessofourmethodinthisparticularcasewetook
theBTFdataofafossilechinitewhichwaspresentedinourpaperaboutrapid

86

5.4.SUMMARY

acquisitionofgeometryandBTFdata[MBK05]andestimatedper-texellocal
coordinatesystemsforitusingthealignmentalgorithmbeforecompressingthe
datausingadaptiveblock-wisefactorization.AsshowninFigure5.6thequality
oftheapproximationissignificantlyimproved,e.g.thebordersbetweendifferent
blockshavebecomealmostinvisibleandthesmall-scalestructuresandshadows
.sharpermuchare

Summary5.4

Inbasedthischaptermeasurementsamethodwaswhichpresented.estimatesIncontrastlocaltocoordinatecomparablesystemstechniquesfromimage-from
thefieldofphoto-metricstereothealgorithmdoesnotrequireassumptionsabout
anlocalunderlyingcoordinatereectancesystemsaremodelbcomputedutoperatesbyfindingdirectlyonrotationsthewhichmeasurements.maximizeThethe
variancecorrelationpresentbetweeninthethedatareectancematrixisfunctionsreducedofwhichthedataleadstomatrix.animproThisvedwayperforthe-
manceoffactorizationalgorithmsbasedonSVD.
theTheSphericalalgorithmHarmonicswasmadebasisefandficientevbyaluatingprojectingthethecorrelationreectanceterminFfunctionsourierspace.onto
ThentheFastFourierTransformationdefinedforfunctionsontherotationgroup,
SO(3),canbeappliedwhichenablesadramaticimprovementinrun-timeper-
O(L8formance.)fortheThedirectcomplesumxitytoOfor(Kthe2Le3vlog2aluationL)byofusingtheFFTcorrelation.isreducedfrom
dataInandtheemeasuredxamplesBTF.presenteThedinresultsSection5.3demonstratethethamethodtthewasdataappliedalignmenttosyntheticachiev-
ablecompressionbythealgorithmperformanceleadsoftomatrixsignificantfvactorizationariancealgorithms.reductionwhichimprovesthe

87

C

HAPTER5

.

ATAD

88

-

D

R

I

V

E

N

L

O

C

A

L

C

OORDINTAES

YSTEMS

CHAPTER6

RELATEDANDCONCURRENTWORK

Wewillcompressioncloseandthemodelicompressionngparttechniquesofthisnotthesisbasedbyonbrieymatrixrefviewingactorization.existingFurtherBTF-
themore,wealignmentwillofintroducereectancegeneralfunctionsphotometricsincetheystereoinspiredalgorithmsourandalignmentotherideasalgorithmfor
forcomputingdata-drivenlocalcoordinatesystems.
ModelsarametricPFitting6.1AsmentionedabovetherowsbˆxofthediscreteBTFmatrixBˆareper-texel4D
reectancefunctionswhichresembleBRDFs.Therefore,itsoundsreasonableto
fittheparametersofananalyticalBRDFmodelf(px;ωi,ωo)foreachrowofBˆ.
Fittinginthiscasemeansfindingasetofparametersminimizingagivenerror
criterion:pxmin=argpminxEbˆx,f(px;∙,∙)
AtypicalerrormetricistheEuclidiandistance.Theresultingspatiallyvarying
coefficientmappxmincanthenbefurthercompressedusinganimagecompression
algorithm.ThisapproachwasintroducedbyMcAllisteretal.[MLH02]andtheyusedthe
Lafortunemodel[LFTG97](Equation2.7).OthermodelsliketheCook-Torrance
model(Equation2.6)havealsobeenusedintheliterature(e.g.[GTR+06]).
real-timeWhilethisreconstructionapproachisiteleturnsgantoutandthatallowsusinghighanalyticalcompressionBRDFratiosmodelsasforwelltheas
depth.representationInthisofcasethereectioninuencefunctionsfromdoesneighboringnotworkforgeometrymaterialsgrowswithstrongeracertainand
ticallyviolatestheindependentassumptionsdistribofutionofanalyticalmicro-fBRDFacets.modThiselslikeresultsinreciprocityalossorofstatis-depth
sentationsimpressionhainvethebeenderenderedvelopedimagesthatastrytodepictedtakeinthesesFigureinuences6.1.intoTherefore,accountrepre-by
usingInmore[MMK04a]compleitxwasanalyticalproposedtorepresentationsinterpretofeachthesampledreectancereectancefunctions.function
89

CHAPTER6.RELATEDANDCONCURRENTWORK

(b)(a)Figure6.1:(a)Photographofarealcylindercoveredwithwhitefabric.(b)Ren-
deredcylinderusingaLafortune-modelSVBRDFfittedtomeasuredBTFofwhite
fabric.Notethelossofdepthimpression(imagesfrom[McA02]).

bˆxasasetofper-view2Dreectionfunctionsbωxothatvarywithlightingdirec-
tion.Theneach2Dreectionfunctionisapproximatedindependentlyusinga
parametricmodellikebiquadraticpolynomialsorcosinelobes.Thisapproach
significantlyimprovestheapproximationqualitycomparedtoBRDF-modelsbut
thefidelitypossiblewithtechniquesbasedonmatrixfactorizationisnotreached
becausebyusinganalyticalfunctionswitharestrictedshapevisuallyimportant
featuresinthedatamightbemissed.Furthermore,thememoryrequirementsare
increasedbyafactorequaltothenumberoffixedviewdirectionsused.
Avariantofthisapproachrequiringevenmorememorybyfittinganadditional
non-linearmappingper2Dreectionfunctionwasproposedin[FH04].

ojectionPrBasisFixed6.2FixedfunctionbasesliketheFourierbasisusedintheDiscreteCosineTransform
(DCT)orWaveletsarequitesuccessfulindata-andespeciallyinimage-compres-
sion.Thissuccesscanpartlybeexplainedbythefactthatanadapteddata-driven
basisusuallydoesnotamortizeinthecaseofimagecompressionbecausethe
spacerequiredtostorethebasisitselfeliminatestheimprovementgainedfrom
thereducednumberofcoefficients.Forhugeimage-baseddatasetsconsisting
ofthousandsofimagesthisrelationchangestowardsthedata-drivenbasis.Asa
resultonlyfewliteratureexistswhichexplicitlyreportsabouttheapplicationof
fixedfunctionbasistransformationtoBTFandrelightableimagedata.

90

6.3.HYBRIDMODELS

Oneexampleisin[WL03]Wongetal.whoinspectedtheper-texeldatabˆx
andprojecteditontotheSHbasis.SincetheSHbasisisdefinedonthesphere
andthereectancefunctionsare4-dimensionaltheSH-transformhastobeap-
pliedtothelightingandviewingdimensionsconsecutivelyyieldingthefollowing
approximation:nmbˆx(ωi,ωo)≈bjkYj(ωi)Yk(ωo)(6.1)
kjHeretheYj(ω)aretheSH-basisfunctionsandthecoefficientmatrixbjkiscom-
projection:doubleusingputedbjk=bˆx(ωi,ωo)Yk(ωo)dωoYj(ωi)dωi.
ΩΩUsingthisrepresentation,typicallycompressionratiosaround1:10canbeachieved
itwwithoutasproposedloosingintoomuch[HWL05]visualtofidelitycompres.sIntheordercoeftoficientsimproveusinguponPCA.thisAdrasituationw-
backoftheapproachistheincreasedrun-timecostsincetheSH-reconstruction
sum(Equation(6.1))hastobeevaluated.Furthermore,high-frequencycontent
likespecularpeakswillbesmoothedoutifhigherordercoefficientsarediscarded
whichmakesSH-basedcompressionsuitableonlyformoderatelyspecularmate-
rials.combinedGenerallywith,mostmatrixoftfhefixactorization,edfunctionasithasbasisbeenalsotransformationdemonstratedtechniquesbycanMabeet
al.[MCT+05]whotransformedBTFdatausingtheLaplacianpyramidbeforethe
applicationofPCA.Thepapershowsalsothathierarchicalfunctionbasescan
betionofhelpfulseveralforfixedrepresentingfunctionmulti-sbasescaledata.(Polynomials,AthoroughSphericalovervieHarmonics,wontheWavapplica-elets)
forcontethextofcompressionimage-basedandsmoothrelightingisreconstructionpresentedinof[MPD2D-reectanceW04].functionsinthe

ModelsHybrid6.3rank.MatrixFforactorizationmaterialswhosetechniquesappearanceworkisoutwelldominatedifthebycovariancehigh-frequencmatrixyhasstochasticlow
distribpatternsutedlikeandpearlescentorientedmetallicmirror-likepaintseffectwhichakescontain(cf.alarFigurege1.1)numberthisofisnotrandomlythe
case.sistsofTherefore,thefolloRumpwingettwoal.parts:[RMS+08]proposedahybridBTFmodelwhichcon-

91

CHAPTER6.RELATEDANDCONCURRENTWORK

(c)(b)(a)Figure6.2:(a)Renderingofmetalliccar-paintBTFusingstandardBTFcom-
pression.Severalartifactsliketilingandblurredspecularreectiondestroythe
realisticimpression.(b)+(c)Thehybridmodelrendersartifact-freeimages(im-
+08]).[RMSfromages

•ThehomogenousBRDFpart,whichdescribesthereectionbehaviorofthe
baseandtoplayerofthepaintandisrepresentedbyamulti-lobeCook-
TorranceBRDFmodel(Equation2.6).Sincemoderneffectpaintscanex-
hibitexcessiveangularcolorshiftsthemodelisextendedbyanangular
table.colordependent•Thespatiallyvaryingpart,whichmodelstheeffectparticlesandconsistsof
smallBTFpatchesfromwhichthehomogenousparthasbeensubtracted.
Duringrun-timethesepatchesarepastedusingatexturesynthesisalgorithm
tocreateanarbitrarilylargetexturewithoutvisiblerepetitionartifacts.

Thiswayhigh-frequencycontentinbothspatialandangulardimensionscanbe
preservedbecausetwodifferentrepresentationsareusedtomodelthem.For
paintsthisapproachisfeasiblebecauseinthiscasethedepthvariationonthe
samplecanbeneglectedwhichallowsarobustfittingofbothpartstoBTFmea-
surementsasdemonstratedinFigure6.2.

MRF-Modeling6.4AnimportantissuewhenitcomestothepracticalapplicationofBTFsistexture
andsynthesisresolution.Sincethe(usuallymeasuredaround256samples2texels)usuallyahamethodveaisquiterequiredlimitedwhichspatialenlarextentges
ontotheserealsamplesgeometrywithout.UsingvisiblesuchsyntrepetitionhesisartifactstechniquesinorderalsotoforwrapeditingthemofBTFsseamlesslywill
bethemaintopicofChapter8.

92

6.5.PHOTOMETRICSTEREOANDALIGNMENTOFREFLECTANCE

Sincetheprincipleoftexturesynthesisistogeneratealargertexturefrom
asmallsampleitcanalsobeinterpretedasadatacompressiontechnique.Ifa
sample-basedtexturesynthesistechniqueinthespiritofEfrosandLeung[EL99]
isused,whichcopiesappropriatesamplesfromtheoriginaltexture,thiscompres-
sionisrealizedofcourseonlyinrelationtothesynthesizedtexture.
Whilethesenon-parametrictexturesynthesistechniquescurrentlyenjoygreat
popularitytherearealsoparametricapproachesaroundwhichtrytorepresenttex-
models.statisticalusingturesPioneeringworkinthisareawasperformedinthegroupofMichalHaindl
atUTIA,Prague.In[HF03]theypresentedaBTFmodelingtechniquebasedon
GaussianMarkovrandomfields(GMRF).Infollow-uppapers3Dcausalauto-
regressivemodels(CAR)[HFA04]andper-subspace2DCAR[HF07]werepro-
posed.Sincethesemodelsusuallyhavedifficultiesinmaintaininglow-frequencyspa-
tialstructurestheyhavetobecombinedwithanapproximate3Dreconstructionof
thesamplewhichcanobtained,e.g.usingphotometricstereo.Duringrendering
thisdepthmapisusedtosimulateshadowingandmaskingeffectswhilethecolor
variationissynthesizedfromthestatisticalmodel.
WhilemodelingBTFsusingparametricstatisticalmodelsisapromisingdi-
rectionforfutureresearchtheapproximationqualityofcurrentlyavailablemodels
doesnotsufficeforhighqualityrendering.

6.5PhotometricStereoandAlignmentofReectance
OurframeswinorkorderfromtoChapterimprove5theisactualperformancelytheoffirstthatmatrixcofmputesactorizationlocalforcoordinatecompres-
sionframesofnotonlyimage-basedforthedatapurposematrices.of3DTheonlyreconstructionmethodbutthatforalsoimprovingcomputesthelocalrep-
resentationofmeasuredmaterialsistheworkofLenschetal.[LKG+03].They
inteparameters.gratedlocalSinceframestheyinassumethefittingisotropicprocessofmaterialsspatiallytheyvonlyaryingneedtoLafortunefitanormalBRDF
vectorLikeperthissurfacemethod,point.ouralgorithmisalsocloselyrelatedtoworkfromthefield
ofphotometricstereoforgeneral,non-lambertianBRDFs+like[GCHS05]which
tionactually5.1canthesebetechniquesinterpretedusualaslydefinegeneralizationaquadraticof[LKGerror03].functionalAsskandetchedinoptimizeSec-
forcorrelationnormalstermandinBRDFordertomodeldetermineparameters.localInframescontrast,andourcomputesmethodrepresentatimaximizesvea
onsampledimprovingreectancedatafunctionscompressioninaandfullynotondata-drianvenaccurateway.3DThereby,reconstruction.ourfocusNevlieser-

93

CHAPTER6.RELATEDANDCONCURRENTWORK

theless,itwillbeinterestingvenueforfutureresearchifourtechniquecanalsobe
reconstruction.3DforusedTheideaofaligningreectancefunctioninordertoimprovethecompression
+ofproposedimage-basedtoreectrenderingsurfacedatalightwasfieldalsodatapursuedaroundbytheWoodnormaletal.in[WorderAAto00].increaseThey
thecorrelationalignmentofofthereectancereectivefunctionspeak.asweComputingdocanabecustominterpretedalignmentasbasedgeneralizationonthe
technique.basicthisif

94

Part

II

Editing

95

CHAPTER7

BACKGROUND

Amaindeficiencyofcompleximage-basedmaterialrepresentationsliketheBTF
isitalthecontentlackofefcreationfectiveeditingapplicationslikmethods.emoAsviesaoradvconsequenceertisementtheisuseofcurrentlyBTFsinlimiteddig-
becausetheseapplicationsrequireadvancededitingcapabilitiesinordertorealize
concept.sdirectorartthepearanceCurrently,inthereComputerareinprincipleGraphics.twoThediffirstferentapproachapproachesisforbasedoneditinganalyticalmaterialandap-
changingproceduralthemodelsinputforparametersreectanceoftheandtemodels.xture.TheHerethesecondappearancetechniqueisuseseditedphoto-by
editingtechniqueslikefiltering,cloning,paintingetc.tomanipulatethetexelval-
uesoftexturemapsdirectly.
resentationsUnfortunatelylike,thebothBTF.Aapproachesmodel-basedcannotbeapproacheasilygeneralicontradictszedthetooriginalcomplexmoti-rep-
vareationvisuallyforinferiorimage-based.Photo-editingmaterials:ausingBTFBTFsusingincasesstandardwhereimage-editingreectancesoftwmodelsare
toolsisdifficultbecauseeacheditingoperationmustbeconsistentlypropagated
dataset.wholethetoseemHotowebeverout,ofsincereachpothewerfulsecondBTF-modelsapproachwithseemsantobeintuitivmoreesetofamendableparameterstogenerstill-
alization.Inordertoapplystandardimageeditingoperationstohigh-dimensional
datadimensionalwestatereprthattwoesentationadditionalofthefeaturecomponentswewareanttorequired.edit.First,Preferablywe,needthisawloouldw-
beasingleimageorasetofcurvesorsliders.Wewillcallthislow-dimensional
representationthefeature-of-interestmodel.Assuggestedbyitsnamethismodel
doesnotneedtorepresentallvisuallyrelevantfeaturesofthematerialwhich
wegreatlyneedasimplifiesback-prtheopagationmodelingmodelstepwhichcompareddescribestoahofullwthematerialeditingmodel.operationsThen
fullwhichhavimage-basedebeenappliedrepresentattoion.theAgain,feature-of-interestthismodelcanmodelbearemuchpropagsimpleratedtothenthea
completematerialmodelbecauseitcanoperateonthedata.

97

CHAPTER7.BACKGROUND

Figure7.1:Theback-propagationbasededitingschemeforhigh-dimensional
data.Theuserhastodealonlywithalow-dimensionalfeature-of-interestmap
whichisderivedusingafeature-of-interestmodel.Thentheappliededitoper-
ationshavetobepropagatedbacktothewholedatausingtheback-propagation
model.

ItisWewillillustratedcallinsuchFigurean7.1editingandschemeconsiststheofbactwok-prmainopagationcomponents:basededitingscheme.
1.Feature-of-interestmodelAneditablerepresentationlikeasetofsliders,curves
orsentationimagesshouldwhichbeallowstocomputableeditafromspecitheficoriginalfeatureofdataininterest.afastThisandrepre-fully
.aywautomatic2.toBack-prbeopagationconsistentlymodelpropagTheatedtoedittheoperationswholedata.appliedUsuallytothenewfeaturedataismaphacreatedve
whichreectsthefeature-specificeditingoperations.
Aclassicalexampleofthiseditingschemeareimage-warpingmethodswhere
a2Drespondimagetoisimportanteditedbyfeaturesinmanipulatingtheaimage.setofUsingcontrolanpointsinterpolationwhichtechniqueusuallycorlik-e
thin-platesplinestheeditingoperationsappliedtosinglecontrolpointsareprop-
agatedtothewholeimage.
arePleasecandidatesnoteforthedifdata-driferenceventoeditinglikedimensionalitydemonstratedreductionbyMatusiktechniquesetal.which[MPBM03]also

98

7.1.TEXTURETRANSFERANDIMAGEANALOGIES

orLawrenceetal.[LBAD+06].Bothapproachesaresimilarinspirittomodel-
latedbased(moreeditingorless)techniquesdirectly.becauseTherefore,the-inthethisvisualcasequalitydata-drithatvencan-bemodelachieisvedmanipu-also
dependsonthecapabilitiesofthemodel.Unfortunately,LawrenceetalsInverse
byShadeonlyTareesfewarefactorsonlyandpracticalitdoesfornotSVBRDFsworkforwhichBTFscanwithbefaithfullymeso-structure.representedThe
data-drivenreectancemodelfromMatusiketal.requiresalow-dimensionalrep-
ingfulresentationinterpolationofawholeofthedatabasemeasuredofmeasuredmaterials.Suchmaterialsawhichrepresentationthenallohaswsnotmean-been
yet.BTFsforfoundTheBTFeditingtechniqueweproposeinthisthesisconsistsoftwodifferent
components.Thefirstcomponent,whichwillbepresentedinchapter8,isbased
vonaaryingback-propagfeaturesofationtheBTFbased.Weeditingsolvetheschemeandback-propagwillbeationusedproblemtoeditbyspatiallyadapting
theImageAnalogiesframework[HJO+01]forBTFs–BTFAnalogies.
Toeditalsothemicro-scalereectanceinthesecondcomponentofourtech-
niqueweproposeaninterpolation-basedapproachresemblingthetexturedatabase
editingofMatusiketal.[MZD05].Itconsistsofinterpolatingbetweendifferent
BTFsbutonlyaftertheyhavebeenmade"compatible"usingourBTFAnalo-
giestechnique–analogy-drivenBTFinterpolation.Aninterestingvariantofthe
techniqueconsistsofacombinationoftheanalogy-driveninterpolationwitha
proceduralmodelformeso-structuretocreateacombinedproceduralanddata-
drivenmodelforleatherBTFswhichforthefirsttimeoffersafullyparameterized
BTFmodelforaparticularmaterialclassandallowsforsmoothnavigationwithin
thespaceofthemeasuredsamples.
BecausetheadaptionoftexturetransferandtheImageAnalogiesframework
iscentraltoourmethodwewillnowgiveashortintroductionintothesetopics.

7.1TextureTransferandImageAnalogies
Texturetransferandconstrainttexturesynthesiswereoriginallydevelopedto
introduceacertaindegreeofusercontrolintotexturesynthesis(e.g.[Ash01]).
Whilepuretexturesynthesisaimsatgeneratinganarbitrarylargeversionofa
smallexemplartexturewithoutvisiblerepetitionartifacts(Figure7.2,left)tex-
turetransfergivescontroloverthesynthesisprocessbydefininganimagewhich
isusedtoconstraintthedistributionoftexturalfeatures.Thisworksfinefor
simpleRGB-textures(Figure7.2,middleandright)butisimpracticalforhigh-
dimensionaltextureslikeBTFsbecausetheconstrainthastobecompatiblewith
thesourcedatainordertoguidethesearchforbest-fittingpixels/patches.Es-
sentially,thismeansthatthetransfertargethastobeaBTF,too,whichwould

99

Figure7.2:Texturetransfer

CHAPTER7.BACKGROUND

leadtoanimpracticaleditingsystem.Furthermore,theapproachisonlysuitable
fortextureswhich(atleastroughly)satisfythestationarityconditionofMarkov
Fields.RandomApossible+solutionisprovidedbytheImageAnalogiesframeworkofHertz-
mannetal.[HJO01]whichaimsatsolvingthefollowingproblem:

GivenapairofimagesAandA(theunfilteredandfilteredsource
images,respectively),alongwithsomeadditionalunfilteredtargetim-
ageB,synthesizeanewfilteredtargetimageBsuchthat

A:A::B:B

IntoBotherinw"theords,samewewway"antastoAfindanrelatestoA"analogous".imageBthatrelates

Whilethisisaquitegeneralproblemwhichcannoteasilybesolvedformany
combinationsofimages,Hertzmannetal.proposedanelegantalgorithmforsolv-
ingtheproblembasedontexturesynthesiswhichworkssurprisinglywellfor
manytypesofanalogies.Forourapplicationofdata-drivenBTFeditingthepower
oftheformulationliesbehindtheintroductionoftheunfilteredsourceimageA

100

7.1.TEXTURETRANSFERANDIMAGEANALOGIES

(Abecauseinthisnowcase)thebutconstraintonlyBwithdoesthenotunfilteredneedtobesourceAcompatible,whichwithcanthebeofsourcesignifi-BTF
cantlylowerdimensionalitythanA.Hence,theimage-analogyframeworkfits
ableperfectlytopropagintoouratechangesback-propagmadeationinabasedsimpleveditingersionofschemeacomple(Figurex7.1)imagesincebackittois
theAcomplegoodxeimage.xampleinthisrespectisthepainting-by-numbersapplicationalso
presentedintheoriginalpaper.Asimple"number-image"alonedoesnotsuffice
tooriginalconstrainimagetheissetsynthesisininacorrespondencemeaningfulwithwanay(Figureappropriately7.3,sebottom),gmentedbutnumberifthe-
imagethingsworkoutquitewell(Figure7.3,middle).Thisexampledemonstrates
thattheapparent"intelligence"oftheImageAnalogiesalgorithmliesmainlyin
thecorrespondencebetweenthecomplexfilteredsourcetextureAandtheless
compleItisxusefulunfilteredtoimaginesourcetethextureImageA.Analogiesframeworkasanextendedcon-
strainttexturesynthesisalgorithmwhichextendsthesourcetexturebyadditional
channelsrepresentedbytheunfilteredsourcetextureA.Duringsynthesisonly
thesewhiletheadditionalotherchannelschannelsarearefullysynthesizedconstrainedpix(byel-by-pixtheelunfilteredusingatarcausalgettextureneighborA-)
hood.Thereby,thealgorithmbalancesbetweenpreservingthestructuresofthe
sourcetexturesandfollowingtheuser-definedconstraint.
versionThisofschemeHertzmannisreectedsmethodinAlgorithm(without2multi-lewhichvelenliststhesynthesis).simplepixel-by-pixel
Algorithm2Pixel-wiseImageAnalogy
inputunfilteredsourceandtargetimagesA,B,filteredsourceimageA
forinitializeeachpixsearchelpinBaccelerationdostructuresforA,A
NB=neighborhood(p,B)
NB=neighborhoodCausal(p,B)
pS=findBestFittingNeighborhood(concat(NB,NB),A,A)
S(p)=pS
orfendreturnSourcecoordinatemapS

101

SourceUnfilteredimage)(numberA

BgetarTUnfiltered

CHAPTER7.BACKGROUND

FilteredSourceA(originalimage)

FilteredTargetedB

Resultusingsimpletexturetransfer
Figure7.3:Painting-by-numbersisanillustrativeexampleforthepowerofthe
imageanalogiesframework.Bycreatingacorrespondencebetweenthesimplified
sourceimageAandtheoriginalimageA,editingofthecomplexoriginalcanbe
inperformedFigure7.2viafailseditinghereBandbecausepropagtheatingalgorithmthecanresults.notdoSimplebettertexturethantryingtransfertolikfite
colors.the

102

CHAPTER8

BTF-ANALOGIES

TheBTF-Analogiestechniquebeingpresentedinthischaptercanbeconsidered
ainChapterprototypical7.Theinstanceoffeature-of-interesttheback-propagmodelationisreprebasedsentededitibynganeschemextractorofintroducedspa-
tiallyvaryingfeatures.Sincethefeaturesareextractedfromtheoriginaldatathe
featuremapandtheper-texelreectancefunctionsareinspatialcorrespondence
automatically.Thiscorrespondenceisexploitedtopropagatetheeditingopera-
tionsBTF-AnalogiesappliedtothebecausefeatureitcanmapbackinterpretedtotasheaBTF.WgeneralizationehaveoftermedHertzmanthissapproachImage
AnalogyframeworktoBTFs.
outinFigurethefollo8.1wingillustratessections.theAccordingcomponentstoofthisourillustrationtechniquethewhichfirstwillversionbeofdetailedour
BTF-analogysystemwouldbethefollowing(comparewithFigure8.1):
FilteredUnfilteredsourcesourceimageimageAAFeaturemapeOriginalxtractedBTFfromtheBTF
FilteredUnfilteredtartargetgetimageimageBBEditedBTFEditedwhichfeaturereectsthemapfeatureedit

Whilethissketchsoundsreasonablethereareseveralproblemstosolveuntil
suchasystemwouldbecomepractical.Thefirstpointisthatthefullcomplexity
oftheBTFisinvolvedinthesynthesisprocesswhichwouldslowdownthealgo-
rithmprohibitively.Thesecondproblemisthefeatureextraction:whatkindof
featuresaresuitableforeditingandhowcantheybeextractedautomatically?The
followingsubsectionswillbededicatedtotheseissues.

AnalogiesImageMulti-Channel8.1Innumbersprincipleofthechannels.basicInImagepracticeAnalogietheschannelalgorithmnumberworksafforfectsimagesmainlywiththearbitrarydimen-

103

CHAPTER8.BTF-ANALOGIES

Figuredimensional8.1:featureBTF-Analogies:maptothefullpropagBTFation.ofeditingoperationsappliedtolow-

sionalityoftheneighborhoodvectorsNBandNB,whichgrowslinearlywith
thenumberofchannels.Foraspatialneighborhoodvectornpwithaneighbor-
hoodradiusofrtexelsandanumberoftexturechannelsc,wehaveforL-shaped
neighborhoods(causal)np∈Rdwithd=(2∗r+1)2/2∗c
IncaseofmeasuredBTFsthenumberofchannelscorrespondstothenumber
ofimagestimesthenumberofcolorchannels(around20.000to70.000forthe
examplesusedinthisthesis).Thisresultsforatypicalradiusofr=2inneigh-
borhoodvectorsizesof240.000to840.000dimensions(themulti-levelversion
ofthealgorithmwouldrequireevenlargervectors)whichisobviouslyinfeasi-
ble.Thesevectorspacesarefartoolargetoperformanefficientsearchforthe
best-fittingneighborhood,whichformsthebasisoftheImageAnalogyalgorithm.
HencethenumberofchannelsoftheBTFhastobereducedbeforebuildingupthe
neighborhoodvectorspace.Otherwise,theneighborhoodsearchwouldbeheav-
ilyunder-constrainedandpracticallyitwouldnotevenbepossibletoconstructa
searchaccelerationdatastructurefortheneighborhoodvectorsbecauseallneigh-
borhoodvectorswouldneedafewhundredgigabytesofstorage(e.g.215GBfor
a256x256texelBTFwith151x151imagesandoatprecision).
Anelegantsolutiontothisproblemistheso-calledAppearanceSpace[LH06].
Theideaistoperformadimensionalityreductionoftheneighborhoodvector

104

8.1.MULTI-CHANNELIMAGEANALOGIES

Figure8.2:Appearancespacetexturesynthesis-bothenlargedresultimageswere
computedusingk-coherancebasedneighborhoodvectorsearch[TZL+02]with
neighborhoodradiusr=1.Ontherighttheappearancespacetexture(first3
channelsareshown)wasusedwhichdrasticallyimprovedsynthesisqualityfor
costs.runtimeequalalmost

spaceandtoperformthesynthesiswithinthisspace.Thetechniqueworksas
follows:d×(w∙h)
textureLetTDcnwith=(enp)xtendp∈[1w...w×]×h[1...hand]a∈Rnumberofbecthechannelsperneighborhoodtexelpdataanddmatrixgivenofasa
above.Standardpixel-wisetexturesynthesiscannowbeinterpretedassearching
foracolumnofDnwhichhasminimumL2distancetotheneighborhoodofthe
currenttexelinthetargettexture.Assketchedabovethissearchisquiteexpensive
evenforRGB-colortexturesandbecomesimpracticalformany-channeltextures
likeBTFs.OnesolutionistoapplyPCAtoDnandperformdimensionalityre-
ductionbykeepingonlykdnon-zeroeigenvalues:D¯nd×≈kCWTwhere(wD¯∙h)n×isk
themean-centeredneighborhooddatamatrixandC∈RandW∈R
arethePCAweightandcomponentmatrices.Thetrickisnowtointerpretthe
weightmatrixWasak-channeltextureTWandtoperformtexturessynthesis
forthistextureinsteadofT.SincenowonetexelpofTWessentiallycontains
theinformationofafullneighborhoodofT,verysmallneighborhoods(typically
r=1)sufficeforahigh-qualitysynthesisofTWandthereforealsoofT.
AsillustratedinFigure8.2thetechniquesignificantlyincreasesthequalityof
standardtexturesynthesisforalmostthesameruntimecost.Anothermotivation
forthetechniqueisitsabilitytofurtherimprovesynthesisqualityby"enriching"
thetexturebyadditional"semantic"channelslikeedgefeaturemapswhichhelp
topreservethefeatureswithnegligibleadditionalrun-timecost.Inthesameway
itisapplicableforsynthesizinghigherdimensionaltexturelikeBTFs.
Theonlyadditionalproblemcomingupisthesizeoftheneighborhoodvector
105

CHAPTER8.BTF-ANALOGIES

datamatrixwhichreacheshundredsofgigabytesassketchedabove.Inorderto
avoidbuildingupthefullmatrixDnweproposetouseoneofthreedifferent
heuristicswhich–fromourexperience–yieldcomparableresults:
1.Applydimensionalityreduction,e.g.PCA,tothemany-channeltexturebe-
forebuildinguptheneighborhoodspace.
2.Useonlyimagesfromthefrontalview(andapplydimensionalityreduction
images).theseto3.Greedilyselectasetofimagesfromthedatawhicharerepresentativefor
thesample.Alternatively,thealgorithmrecentlypresentedin[FCGH08]
used.becouldwillSinceusuallythecomputeappearanceappearancespaceisspacesuchateusefulxturesealsoxtensionforthetotextureunfilteredsynthesissourceandwe
targetfeaturetextures.Therefore,theBTFanalogiesalgorithmcanbeformulated
ws:folloasAlgorithm3Pixel-wiseBTFAnalogy
inputunfilteredsourceandtargetfeatureimagesFa,Fb,BTFG
BA=appSpaceT=appSpaceTeexture(xtureProj(Fa)F)
bGred=btfDimReductionHeuristic(G)
A=appSpaceTexture(Gred)
S=Algorithm2(A,B,A)
returnSourcecoordinatemapS

Pleasenote,thatbothGredandAneedtobecomputedonlyonceforeach
BTF.AneedstobecomputedonlyonceperfeatureperBTFwhichmeansthat
itcanbeprecomputedforeachBTFandfeaturetypecombination.Therefore,
duringeditingweonlyneedtoprojectFbontheappearancespaceofFa,which
isquitecheap,andthenperformAlgorithm2,whichisthemostcostlyrun-time
partoftheBTFanalogyalgorithm.Ifthemulti-levelversionofthealgorithm
isused,theinputpyramidsAandAandalsotheneighborhoodsearchaccel-
erationdata-structurewhichconsistsoftheconcatenatedneighborhoodsfromA
andAcanalsobepre-computed.Inourimplementationweusethek-coherance
search[TZL+02]asaccelerationstrategywhichleadsinourun-optimizedandun-
parallelizedprototypeimplementationtosynthesistimesofabout2-4secondsfor
atextureof256x256texelsinsize(IntelE6400CoreDuowith3GBRAM).This

106

8.2.FEATURESFORBTFANALOGIES

isalreadynotfarfrombeinginteractiveandanoptimizedversionofthealgorithm
willbeundoubtedlyevenmoreresponsive.

8.2FeaturesforBTFanalogies
Inthissectionwewilldiscusstwodifferenttypesoffeaturesthatcanbeusedfor
BTFeditingbasedonBTF-Analogies.Thesimplestfeaturewillbeasinglecolor
imagethatcanbechosenfromtheoriginalBTFdata.Aswewillseeinthefollow-
ing,onlyrelativelysimpleeditingoperationscanbesuccessfullypropagatedback
tothefullBTFthisway.Especiallymaintainingconsistentshadingeffectsfor
complexmaterialsisdifficult.Therefore,wealsodemonstrateeditingbasedon
reconstructed3Dinformation,i.e.adepthmap.Usingthismoreelaboratefeature
map,shadingeffectswillbepreservedmorefaithfully.

imagesRGB/LuminanceSingle8.2.1Formostmaterialsasingleimagecapturesalreadymanyimportantfeatures,espe-
ciallyifthereectancebehaviorissimpleandthemeso-structureisapproximately
at.Inthiscaseitcanbeexpectedthatsimpleeditingoperationslikedeleteor
copycanbepropagatedwellalreadybyeditingonlyasingleRGBorluminance
image.

height-mapReconstructed8.2.2BTFsareespeciallyinterestingforrepresentingmaterialswithasignificantmeso-
structure,becauseshadowing,maskingandhigherorderlight-transporteffects
aredifficultandcostlytosimulate.Atleastthefirstorderlighttransporteffects
likeshading,shadowingandmaskingwhichusuallymakeupthemajorcompo-
nentofappearancearealreadywelldescribedbyadepthmap.Thisfactwas
alreadyrecognizedbyLiuetal.[LYS01]whosynthesizedBTFsusingrecon-
structedmeso-structure.TheirmaingoalwastosynthesizeacontinuousBTF
fromthesparseBTFsamplesofferedintheCUReTdatabase[DvGNK97].To
synthesizeanovelview/lightconfigurationtheyrenderedthesynthesizedmeso-
structurewiththecorrespondingviewingandlightingparametersandusedthe
resultingimageasguidanceforcopyingappropriatesampleblocksfromthecap-
turedimages.Thereby,theywereabletoenforceconsistencyacrossdifferent
view/lightconfigurations,althoughtheysynthesizedeachimageoftheBTFinde-
.pendentlyFortunately,duetotherecentprogressinBTFmeasurementmethodology
muchmoredenselysampledBTFdatathantheoriginalCUReTdataisnow
107

CHAPTER8.BTF-ANALOGIES

anovvelailable.view/lightThesedatasetsconfigurations.canbeusedInstead,withoutwetheproposetorequirementusetheofreconstructedsynthesizing
meso-structureaslow-dimensionalrepresentationwithintheBTF-imageanalo-
ork.wframegiesThefirstrequirementhereistoreconstructtheheightmapofthematerial.Re-
right.constructingSinceourthesamplesmeso-geometryareonlyoftemoderatelyxturesisanglossyactivandeourresearchmethodtopicdoesinitsnotode-wn
pendonaperfectlyaccuratereconstructionwefoundclassicalphotometricstereo
iments.techniquesTo[RincreaseTG97]theandnormalreconstructionintegrationquality[FC89]fortomorebesufspecularficientformaterourialseitxperis-
orepossibleventoourousewnsuitabledata-drivenreconstructiontechniquefromtechniquesChapterlike5.thatofChenetal.[TCS06]
Figure8.3showsresultsofthephotometricmeso-structurereconstructionfor
somemethodofistherobustmaterialsagainstusedlointhisw-frequencthesis.yPleaseerrorsnotetypicallythatthepresentconstraintinphotometricsynthesis
reconstructionssinceitisbasedonlocalfeaturesimilarity.

ComputingDerivedFeatures
Duringourexperimentswediscoveredthatadditionalfeaturesderivedfromthe
height-maphelptoimprovethesearchforbest-matchingneighborhoodsinmany
cases(seeFigure8.4).ThisisawellknownissueoftheL2-normwhich+iscom-
monlyusedforneighborhoodcomparisonintexturesynthesis(cf.[ZZV03]and
[LH06]foramorein-depthdiscussionofthistopic).Theadditionalfeatureswe
derivefromtheoriginaldepthmaparenormalvectorsandview-dependentocclu-
sion.Tocomputethenormalvectorswesimplyconvertthedepthmapintoatri-
angularmeshandcomputetheper-texelnormalsbyaveragingthenormalsof
triangles.adjacentComputingocclusionsisalittlebitmoredifficultbecausedoingitstraightfor-
ward,e.g.usingray-tracingwouldbefartoocostlyforinteractiveediting.There-
fore,weemploygraphicshardwaretorapidlycomputeocclusionsviashadow
mapping.Ourimplementationisabletoprocessabout500viewdirectionsper
secondfora60kverticesmeshonaNVidia8800GTX.Thissamplingresolution
typicallysufficestoreliablycomputea4th-or5th-orderSphericalHarmonicsex-
pansionoftheview-dependentocclusionwhichisthenusedasfeaturemap.
Byusingtheappearancespacetechniquetheseadditionalfeaturescanbein-
corporatedintoAlgorithm3withnegligibleadditionalrun-timecostsbycreating
amulti-channeltexturefromthedepth-,thenormal-andtheocclusion-mapand
computingtheappearancespacetexturefromit.

108

8.2.FEATURESFORBTF

PLASTER

ANALOGIESTHERLEA

THCLO

WOOL

Figure8.3:Meso-structurereconstructionsofthematerialsusedinthisthesis.
Fromtotobottom:frontalview,normals,depth,appearancespace.Allresults
wheregeneratedusingphotometricstereoandnormalintegration.Thenormal
mapsareshownusingthestandardRGBencoding.Theappearancespaceimage
visualizesthefirstthreePCAweights.

109

CHAPTER8.BTF-ANALOGIES

Figure8.4:UsingadditionalgeometricfeaturesfeaturesimprovesBTFAnalogies.
Fromlefttoright:OriginalBTF,depthconstraint,resultusingonlydepthfeature,
resultusingalsonormalvectorsandview-dependentocclusion.

8.3ResultsandExperiments

FortestingtheBTF-Analogyalgorithmandthepresentedfeaturerepresentations
wecreatedthreedifferentandpracticaleditingscenariosandinvestigated,how
rialwellandthefeatureeditingtypes.operationsWeusedarethepropagfouratedtomaterialswholedepictedBTFindependingFigureon8.3.themate-
TheresultsareshownforeachmaterialinFigures8.5–8.8,andtheyarealways
terialpresentedandasthefollows:feature-of-interestForeachmapsmaterialwhichweshoarewaeitherarenderingfrontalofvietheworiginalimagewithma-
averagedlightingoranapproximatedepthmap.Furthermore,weshowanim-
ageofthefirstthreechannelsoftheappearancespacetexturecomputedfromthe
spacetedimensionalityxturesinreducedFigureBTF8.3which(whichwereshouldnotcomputedbefromconfusedthewiththeapproximateappearancedepth
mapandthecorrespondingfeatures).Weusuallykeptthefirst64PCAcompo-
7x7nentstexandels.Thecomputedresultsaarethen12D-appearanceshownspacetogethertexturewiththeusingaeditedfeatureneighborhoodmaps.sizeof

aintingP8.3.1Thisapplicationisinspiredbythepainting-by-numbersexamplefromtheoriginal
ImageAnalogiespaper.Theideaistousethewell-knownpipetteandcloning
toolstoselectvaluesandregionsfromthefeature-of-interestmapandtopaint
withthemanovelimage.Duetotheauthorsquitelimitedpaintingskillsthetask
waschosentobesimplebutexpressive:asmilingstick-figureface.
Ascanbeseenintheimagesboththergb-imageandthedepth-featurecontrol
mapsaresuitablefortransferringtheeditingoperationstotheBTF.Theresults
achievedusingdepthmapsareslightlysuperiorintermsof3D-structurepreser-
vationasprovenbytheresultsforthePLASTERandLEATHERmaterials.On
theotherhandthesimplergb-imageperformsbetterinpreservingtheweaving

110

8.3.EXPERIMENTSANDRESULTS

patternofthegoldfabricpartfromthecloth.Thisisprobablyowedtothefact
thattheweavingpatternwasnotwellcapturedinthedepthmap.Thewoolma-
terialinformationshowsisanothermainlylostinterestingattheeffectlocationhere:ofForthetherpaintgb-imagestrokesthebutthehigh-frequencgeometryy
ofthemainthreadsisstillpreserved.Forthedepth-featurethealgorithmtriesto
preservealsothehigh-frequencyinformationofthesub-threadswhichrendersthe
prominent.lessappearediting

pingarW8.3.2Aneditingoperationwhichshouldbeaslightlyeasiertaskforthealgorithmis
warpingthefeature-of-interestmap.TheideaistotaketheFOImapandapplya
ofwpixarpingelsandoperationaresamplingwhichofbasicallythecorresoriginalpondsdata.toaThesespatiallyoperationsvaryingshouldtranslationeasily
bereproducedbythemethodbecausetheneighborhoodsearchshouldbeableto
translations.arpwthetrackForthecreationourexamples,whichconsistofafewswirlsineachimage,
weusedtheIWarp-FilterfromtheopensourceimageprocessingsoftwareGIMP1.
Asexpected,fortheseoperationsthemethodproducedmoreorlessmeaningful
resultsevenforthewoolmaterial.Again,thedepthfeature(especiallywhen
extendedbythederived,additionalnormalvectorandocclusionfeatures)achieves
resultswhicharemoreconsistentwiththeoriginalBTFappearance.

ransferT8.3.3someWhileethexperimentsfirsttwowithapplicationscompletelymainlydifferentconsistfeatureofeditingmapsthewereoriginalmade,too.FOImapThis
resultsoperationdepictedcouldbehereweinterpretedusedanasimagesomeofsortofcobblestonestexture-to-BTFastransfertransfertarget.teForxture.the
Ofcourse,thefeaturesandstatisticspresentinthetargettextureshouldberoughly
findrelatedenoughtotheBTFsmeaningfulFOImapmatches.becauseSuchafotherwiseailurethecaseisalgorithmthewoolsimplymaterialwouldwhichnot
hasameso-geometryquitedifferentfromthecobblestones.
Thisinterpolation.kindofThiseditingwayoperationfeaturesisof,ofe.g.particulardifferentinterestleatherswhenorittecomesxtilestocouldmaterialbe
transferredbetweeneachotherinordertoallowamoremeaningfulinterpolation
aswillbedetailedoutinthefollowingChapter9.

1http://www.gimp.org

111

CHAPTER

8.

BTF-ANALOGIES

Figure8.5:EditingresultsforthePLASTERmaterial.Usingdepthasfeature-of-
isinterestmostnotablegenerallyforimprothevestransferthepreservoperationationwhereofthedepth-relatedappearancefeatures.oftheThisscratcheseffect
andvalleysispreserved.

112

8

.

3

.

E

XPERIMENTSANFigure

DR

E8.6:

SUTLSEditing

results

for

113

the

THERLEA

material.

Figure

8.7:

Editing

results

for

114

the

C

HATHCLO

PTER8

.

B

material.

T

F

-

A

NALOGIES

8

.

3

.

E

XPERIMENTSANDFigure

R

ESU8.8:

TLSEditing

results

for

115

the

OOLW

material.

116

C

HAPTER8

.

B

T

F

-

A

NALOGIES

CHAPTER9

ANALOGY-DRIVENBTFINTERPOLATION

TheBTFAnalogiestechniqueintroducedinthepreviouschapterisalreadyapow-
erfultooltoeditandmanipulatespatiallyvaryingfeaturesofmeasuredBTFs.
However,applyingtheeditingoperationstoachieveadesiredgoalcanstillbea
difficulttaskandmightrequireartisticskills.Furthermore,thetechniquedoesnot
allowtoeditthemicro-scalereectancebehavioroftheBTF.
Inthischapterwepresentanalogy-drivenBTFinterpolationwhichprovides
solutionstothesetwoproblems.BasedontheBTFAnalogyalgorithmthisinter-
polationallowstochangethemicro-scalereectancebehaviorofBTFsinafully
data-drivenway.Furthermore,asillustratedinFigure9.1,bygeneratingacom-
monfeature-of-interestmapusing,e.g.aproceduraltexturemodel,newBTFscan
becreatedbythemanipulationofafewslidersonly.Theideaistoutilizethe
proceduralmodelforthegenerationoftheFOImapwhichthenisusedasinput
fortheBTFAnalogy.ByemployingthesameFOImapformultipleBTFsthe
interpolationbetweentheseBTFsbecomesmeaningfulsincetheimportantspa-
tiallyvaryingfeaturesareallalignedtothissingleFOImap.Usingthisapproach
ahybridproceduralanddata-drivenmodelforaspecificmaterialclasscanbe
generated.InthefollowingwewilldetailouttheefficientinterpolationofmultipleBTFs
inSection9.1.Thenaproceduralmodelforleathermeso-geometrytextureswhich
exemplifiesourideaofahybridproceduralanddata-drivenmodelwillbeintro-
ducedinSection9.2.Theclosureofthischapterconsistsofpresentingexperi-
mentsandresultsinSection9.3.

BTFsMultiplepolatingInter9.1Astraight-forwardimplementationofFigure9.1ispossiblebutresourceintensive
sincetheBTFAnalogyalgorithmisperformedindependentlyforeachoftheinput
BTFswhichhavetobekeptinmainmemory.SinceitislikelythattheinputBTFs
arefromthesamematerialclassitcanbeworthwhiletoexploitinter-materialcor-

117

CHAPTER9.ANALOGY-DRIVENBTFINTERPOLATION

FigureAnalogies9.1:areusedMeaningfultoalignBTFthespatiallyinterpolationvaryingdrivenbyfeaturesBTFtoaAnalogies.commonThefeature-of-BTF
BTFsinterestcanmap,bee.g.linearlygeneratedcombinedbyawithproceduraluser-definedmodel.scale-fThenactors.thesespatiallyaligned

118

9.2.PROCEDURALLEATHERMESO-GEOMETRY

relations.Infact,interpolatingBTFsfromcompletelydifferentmaterialclasses
likeshinymetalandwoolclothmightbefunnybutitdoesnotmakemuchsense
forpracticalapplications.Itismorereasonabletocombinematerialsfromrelated
materialclasses.Inthiscasethespatiallyvaryingfeaturesaremorelikelytohave
similarstatisticswhichimprovestheresultsoftheBTFAnalogy.
Onepossibilitytoexploittheinter-materialcorrelationswouldbearranging
eallxtendedmaterialstensorin.atensorConsideringwithantheresultsadditionalfrommaterialChapter4modeweandproposetofaactorizedifferentthis
strategybasedonblock-wisefactorization:
keepFirst,thefirstwef150actorizetheEigenimages.dataThismatrixofusuallyeachsufficematerialtousingreducesthestandardwholeSVDdataandto
asizethatfitsintomainmemory.Thenweperformaninter-materialspatialclus-
weteringfactorizebasedtheontheseoriginaldataEigenimages.ineachWeclustertypicallyandkeepusedaboutabout8-10250eigenvclusters.ectorsThenper
clustertoallowforfastevaluationduringrun-time.
Now,meaningfulinterpolationduringeditingcanbeafforded.Forexample,a
setmodeloffromperceptuallyMatusikmeaetal.ningful[MPBM03]directionscaninbethespiritdefinedofforthethedata-drimaterialvenclass.reectanceEach
materialwillbeassignedascorealongtheparticulartraitvector(e.g.byperform-
ingasimpleuserstudy).Thesescoresthendeterminetheinterpolationweights
fortherespectivematerialwhentheuserchoosesparticularvaluesforthedifferent
traits.Duringeditingforeachmaterialinthedatabase,whichhasbeenassigneda
weightsynthesis.largerThisthanareturnssmallasetofthreshold,referencesweperformintothetheBTFdatameso-structurewhichareconstraintused
tolookupandreconstructtherespectivereectancevaluesfromthecompressed
database.Thenthesevaluesareinterpolatedusingthegivenweights.Resultsof
ourmethodaregiveninSection9.3.

Meso-GeometryLeatheroceduralPr9.2Wewillnowexemplifyourideaofahybridproceduralanddata-drivenmaterial
model.Sincethedata-drivenpartofthemodelisrepresentedbyasetofBTFsand
theBTF-Analogytechnique,theonlythingleftistheproceduralmodelwhich
isintendedtomodelthefeature-of-interestmapofaspecificmaterialclass.In
ordertogiveinteractivefeedbackduringeditingsuchamodelshouldbeefficiently
computable.Furthermore,thepossibilityoffittingthemodeltothemeasurements
isdesirableinordertostarttheeditingprocessfromameasuredsample.Last,but
notleast,itwouldbeadvantageousthatthemodelsupportssmoothinterpolation
betweendifferentinstancesofthemodelinordertosupportsmoothinterpolation
119

CHAPTER9.ANALOGY-DRIVENBTFINTERPOLATION

Figure9.2:Left:Realleathertexture.TheanalogytoatypicalVoronoicrack
patterngivesthetypical"Voronoi-look".Ourmodifiedcrackpatternwithpolyline
basedsitesanddepthvariationoffersamorenaturalvariationofsiteshapes.

materials.ferentdifofAmodelsatisfyingtheserequirementsforleather-likematerialswillbepre-
sentedinthefollowingsubsections.However,bydefiningappropriatefeatures
andcorrespondingproceduralmodelswebelievethatourtechniquecanbeap-
pliedandgeneralizedtomanyotherinterestingclassesofmaterialslikeclothor
ood.w

9.2.1ProceduralVoronoiCrackPatterns
Thereexistmanyalgorithmswhichtrytosimulatebiologicalorphysicalcrack
patterngenerationprocessesresemblingtheappearanceoftypicalleathercrack
patterns(therecentpaperofIbenetal.[IO06]givesagoodoverview).Unfor-
tunately,mostofthesemethodsaretypicallynotinteractive.Therefore,com-
mercialleathershadersareoftenbasedonWorleyscellulartexturebasisfunc-
tion[Wor96]whichgeneratescracksbycomputingtheVoronoidiagramofran-
domlydistributedsitesandcanbeevaluatedveryefficiently.Thedrawbackofthis
methodisthatthegeneratedVoronoisiteshaveanotveryrealisticshape.Further-
more,weneedamethodtocontrolthegenerationofcracksofdifferentdepths
whichisusuallynotsupportbytheseWorleyshaders.
Weproposetwosimplebuteffectivesolutionsfortheseshortcomings.The
firstideaistocomputethegeneralizedVoronoidiagramofpolylinesinsteadof

120

9.2.PROCEDURALLEATHERMESO-GEOMETRY

points.Thisallowstogeneratemorerealisticallyshapedsites.Thesecondtrickis
tobasethecrackdepthonthedistancetothecenteroftheneighboringsites.
Thedistributionofthesitescanbecontrolledwitharbitrary2D-densityfunc-
tions.BydefaultweusearandomlygeneratedPerlinturbulencetextureasdensity.
Thedegreeofrandomnesscanbesetbytheuserandcontrolsthe"spotiness"of
thecracktexture.Theshapeofthesites,i.e.their"roundness"and"anisotropy"
canbecontrolledbysettingaveragelength,preferredorientationandregularityof
thepolylines.AsillustratedinFigure9.2thesemodificationsoffermorevariety
intheshapeofthesitesandthusrepresentamoregeneralclassofleather-like
materials.

9.2.2EfficientCrackPatternComputation
Thecomputationofacrackpatternfromtheaforementionedparameterscanbe
doneveryefficiently.WeusethealgorithmofKopfetal.[KCODL06]todistribute
thesitesgivena2D-density.Tocomputethecrackpatternfromthesiteswe
employtheGPU-baseddrawingalgorithmforgeneralizedVoronoidiagramsby
Hoffetal.[HKL+99].Afterassigningadepthtoeachcrackweuseadepth-
dependentGaussiancrackprofiletodrawthecrackheightfieldintothez-Buffer.
Thisprocesscanberepeatedfordifferentscalesandweallowtocombinethese
scaleswithuser-definedfactorsandtoapplyGaussianfilteringtoeachofthe
.independentlyscales

9.2.3MorphingProceduralCrackPatterns
Agreatadvantageofourproceduralmeso-geometrymodelisthatnaturalmorphs
betweendifferentinstancesofthemodelcanbecomputedeasily.Inourcasethis
isnotdonebyinterpolatingthemodelparametersbutbyfindingcorrespondences
betweenthesites.Inparticularwecomputecorrespondencesthatminimizea
morphingdistance.Thenwemorphthestructurebyinterpolatingpositionand
sites.correspondingtheofstructureOurmorphingdistanceisdefinedasfollows:A={ai}0<i≤MandB=
{bi}0<i≤NshallbethepolylinebasedVoronoisitesoftwocrackpatternswith
M≤N.Thenthemorphingdistancewetrytominimizeissimply
MD(A,B)=minfdλ(ai,bf(i))
=0iwherefisaninjectivemappingbetween{1...M}and{1...N}.Findingthe
assignmentfwhichminimizesDisaclassicalcombinatorialoptimizationprob-
lemwhichcanbesolvedefficientlyusingtheHungarianalgorithm[Kuh55].The
121

CHAPTER9.ANALOGY-DRIVENBTFINTERPOLATION

Figure9.3:Fittingtheproceduralcrackpattern.Left:OriginalBTFwithdepth
mapandcracks(ingreen)foundbywatershedalgorithm.Right:Resulting
VoronoicracksandrenderedresultcomputedbytheBTF-analogyalgorithm.

distancedλbetweentwositesai,bjisdefinedasaweightedsumoftheEuclidean
distancebetweenthecentersofgravitycog(∙)oftheVoronoisitesandashape
distanceds(∙,∙)betweenthesitebordersoftheVoronoisites:

dλ(ai,bj)=λ|cog(ai)−cog(bj)|+(1−λ)ds(ai,bj)

Therearenumerouswaystodefinethe2Dshapedistanceds.Weusedtheapproach
ofSederbergandGreenwood[SG92]whichisbasedondynamicprogramming.
Thistermcanbeusedtoenforcethattheshapesoftwositesthatareblended
togetherareroughlysimilar.Typicallywechooseλcloseto1sinceamorphwith
aminimalmovementofsitesusestobethevisuallythemostpleasant.
Themorphingitselfisbasedoninterpolatingthecentersofgravityofthesites
andmorphingthepolylinesthemselvesisalsobasedonSederbergandGreen-
wood.Sincethenumberofsitestypicallydoesnotmatch,thenumberofsites
isequalizedbygeneratingnewsiteswhicharesmoothlyblendedinduringthe
morphing.

122

9.3.EXPERIMENTSANDRESULTS

9.2.4FittingCrackPatternstoMeso-Geometry
lowsFittingtherepresentingcrackrealpatterntemeasuredxturetorealmaterialsmeso-geometrycompletelyiswithindesirableourmodelbecauseanditthusal-
tostarteditingthisrepresentationfromarealmaterial.
Inthecaseofcrackpatternsthefittingcanbereducedtoacomputervision
task.Firstwedetectthecracksinthemeso-structureheightfieldusingavariantof
aaxiswatershedtransformimageofthesefoundgmentationcrackpatternalgorithmto[RM00].determinetheThenwecorrespondingcomputeaVmedialoronoi
tendssites.toSincelooseweabitofcurrentlyinformationonlyallowduringsimplethisstep.polylinesAsasVillustratedoronoiinsitesFigurethe9.3processthis
procedurereconstructstheoverallshapeanddistributionofcracksandsiteswell.
tionComparingcanbethespottedrenderedintheimagesreconstruction.closelyaslightApparentlylossof,thiskindhigh-frequencofyinformationinforma-
cannotbecapturedbyasimplecrackpattern.

ResultsandExperiments9.3

Inordertotestouranalogy-drivenBTFinterpolationwesetupadatabasefif-
teendifferentrealandimitatedleathermaterialsshowninFigure9.4.Again,all
thesematerialshavebeenmeasuredattheUniversityofBonn.Themeasurements
havebeencuttoaspatialresolutionof128x128texels.Sinceabout20000HDR
images(RGB)arecapturedpermaterialtheuncompressedstoragesizeofthis
databaseisabout30Gigabytes.UsingBTFcompression(adaptiveblock-wise
factorization)thestoragerequirementsforeachmaterialcanbereducedtoabout
5-10megabytesleavinguswith100Megabytesforthewholedatabasewhichis
alreadymanageable.Wecanreducetheserequirementsbyanadditionalfactorof
morethan50%withoutreducingvisualqualitybyexploitinginter-materialcorre-
lationsasproposedinSection9.1.
Acomparisonbetweenouranalogy-driveninterpolationandnaiveinterpola-
tionisshowninFigure9.5.Thebottom-leftimageshowstheresultofnaive
interpolationbetweenthreeleatherBTFsandaplasterBTFbyinterpolatingeach
per-texelreectancefunction.Thenaiveinterpolationresultsinablurredmeso-
structurewhichdoesnotappearveryrealistic.Thebottom-rightshowsthere-
sultofinterpolatingthesameBTFsbutonlyafterthespatialalignmenttoa
commonmeso-structureusingtheBTFAnalogytechnique.Thecommonmeso-
structurewasgeneratedusingourproceduralmodelforcrackpatternsintroduced
inSection9.2.Theinterpolatedresultshowsamuchsharperandmorerealistic
meso-structurewhilethemicro-scalereectanceappearsasaquiteinterestingand
meaningfulmixofthedifferentmaterials.

123

Figure

9.4:

CHAPTER9.

Fifteen

ferentdif

124

ANALOGY-DRIVENBTF

e-likleather

materials.

INTERPOLATION

9.3.EXPERIMENTSANDRESULTS

+

+

+

=

+

+

+

=

Figure9.5:NaiveinterpolationofthedifferentleatherBTFsresultsinablurred
meso-structure(left).UsingBTF-AnalogiestocreateBTFswithsimilarmeso-
structureenablesamoremeaningfulBTFinterpolation.

125

CHAPTER9.ANALOGY-DRIVENBTFINTERPOLATION

Figure9.6:Editingofthe"dragonsskin".Left:MeasuredBTF,middle:making
theincreasingmeso-structureglossinessmoranderegularshifting,givingcoloritamakesmorethespottydragon,looklizard-likaelittlelook.bitRight:more
vil.e

shownAninexampleFigure9.6.forTheeditingaoriginalleathermaterialBTFisusingmademorecharacteristic"specular"materialandtraits"reddish"is
byFurthermore,mixinginthematerialsleatheriswhichmadehavemorebeenregularassignedbyhighchangingscoresthealongparameterstheseoftraits.the
model.proceduralFinally,Figure9.7showsanexampleofasmoothmorphbetweentwomateri-
alsfromthedatabase.Itsmoothlyinterpolatesthestructureandreectanceofthe
etwvoenbetterleathers.impressionPleasetakofethealsoanaturalnesslookattheoftheaccompancomputedyingwarp.videowhichgivesan

126

.9.3

EXPERIMENTS

DNA

R

ESUTLSlarFigurestructure.9.7:TheMorphingmorphedbetweenconstraintgrayteleatherxtureandisashobeigewnabovimitatedeeachleatherrenderedwithreimage.gu-
Thereectanceisinterpolatedandrenderedfromthemeasurementsstoredinthe
database.BTFcompressed

127

C

HAPTER9

128

.

A

AN

L

O

G

-Y

D

R

I

V

E

N

B

T

F

I

NTERPOLTAION

CHAPTER10

RELATEDANDCONCURRENTWORK

Theeditingofhigh-dimensionalmeasuredappearanceisarelativelynewresearch
asareawellbutasitteisxturebasedonsynthesisagreatanddealtransferofworkfromfromwhichthewefieldswillofonlyappearancementionthemodelingmost
ork.wrelated10.1AppearanceModelingandEditing
Measuringreectanceandfittinganalyticalmodelstothedataasintroducedby
Wtationard[Wcanar92]easilyhasbealongeditedtimebytraditionchanginginthecomputerparametersofgraphics.theSuchanalyticalarepresen-model.
Matusikanalyticaletal.reectance[MPBM03]modelsonlyquestioneddescribethisameasure-fitrestrictedclassparadigmofbymaterialsclaimingandthatthat
theirproposedaparametersdata-drioftenvenhavereectancenointuitimodelvephbasedysicalonalarmeaning.gecollectionCoofnsequentlymeasured,they
BRDFsandapplieddata(manifold)analysisandperceptualstudiestofindper-
ceptuallymeaningfuldirectionsinthespaceofthesemeasuredBRDFs.While
suchanapproachseemstobefeasibleinthecaseofBRDFsnoanaloguemodel
hasbeenproposedforspatiallyvaryingreectanceyet.
WeyrichInstead,etal.dif[WMPferent+06]approachesforinstancesuitableproposedforaasinglematerialmeasurement-basedhavebeenreectancetaken.
tialmodelvforariationhumanoftheskinskinisbasedoncapturedtheinTsimpleorrance-SparroalbedowmapsBRDFwhichmodel.canbeThetrans-spa-
Berferredgenbetween[HB95].facesUnfortunatelusingthey,suchhistogramanapproachequalizationisinfeasibletechniqueforofmaterialsHeegerwithand
depthvariationbecauseinthiscaseanalyticalreectancemodelsperformpoorly
[MMK04a].Thenon-parametricInverseShadeTreeapproachbyLawrenceet
al.[LBAD+06]allowseditingofmeasuredspatiallyvaryingmaterialsbutthe
usedlow-termfactorizationsagainrestrictthemethodtoatmaterialswhichcan
bedescribedbyafewbasisBRDFsonly.
whoThefirstintroducedmethodBTFShopdealing:withphoto-editing-liknon-atematerialsmanipulationisbyofKautzBTFets.al.Among[KBD07]the

129

CHAPTER10.RELATEDANDCONCURRENTWORK

proposededitingoperatorsaretoneandcoloreditingusingdifferentialpainting
andlarityachangendalsoofquitecolorgeneraldistribution,toolslikeangularCopyblur&Pandastesharespectingrpeningforparallaxeditingandspecu-shad-
owing.Someoftheseoperatorsliketheangularblurorthetonaloperatorsare
appliedheuristicstothethatcanwholebedatausedtoaftermimictheuserhasmodificationssettheiroftheparameters.micro-geometryOtherandoperatorsare
likingethemcolorfrompaintingthetopgeneralizeviewtobasicallothertoolsknoimageswnfromusing,imagee.g.difeditingferentialbyedits.propagat-In
ordertoaccountforparallaxbetweendifferentviewsinthiscasetheauthorsde-
finewarp/unwarpoperatorsbasedonanapproximategeometricreconstruction.
ingThethesystemrawperoperatestexelaldata,waysandonittheachiefullvesBTFinteractidata,vi.e.epeeditsrformanceareappliedbybyemployingmodify-a
Whensophisticateditcomesout-of-coretothedataeditingofmanagement.thespatialdistributionoftexturalfeatures
BTFShophasthesamedifficultiesastraditionalimageeditingsoftware.For
exampleoperationsischangingratherthepatterncumbersome.ofaAlsostoneweditingalltheusingpaintreectancetooltoswandardscuta&specificpaste
existinginterpolationmaterialareisspecificallyratherdifficult.designedSincefortheseBTFtasksanalogiesitisandeasytodata-drivimagineenBTFthat
ourtechniquecanbenicelyintegratedwithinBTFShopasanadditionalediting
operatororthogonaltotheonespresentedinthepaper.
andLaAnotherwrencetechnique[PL07].ItisorthogonaldesignedtoourstoisthespatiallyAppWpropagandatealgorithmeditsofbyreectancePellacini
propertiesappearance.byTheofferingtoolabehavesgeneralizedanalogouslywandtotoolanwhichimagewselectsandretoolgionswhichofselectssimilar
regionsofsimilarcolors.Theeditisactuallyperformedbyoffsettingandscal-
theingamethoddesiredpropagparameteratesvthealueeditsfortheconsistentlysamplestoselectedregionsbyofthewsimilarandtoolandappearance.then
tiallyTherebyv,itaryingismainlyparametricsuitableBRDFforatmodels.materialsAmorewhichgeneralcanbeformulationrepresentedofthebyspa-edit-
ingpropagationobjectivefunctionwhichdoesnotarelyonasparseneighborhood
graphhasbeenrecentlypublishedbyAnetal.[AP08].
Thesemethodsaredesignedtoconsistentlypropagateparametriceditsacross
tecomplexturalxspatfeaturesialasitpatterns.ispossibleTheyarewithnotoursuitablemethod.foreditingspatialdistributionsof

10.2Texturesynthesisandtransfer

Theparametricinherenttexturecomplemodel.xityofteInsteadxturemodelshaspreforventedspecialthetypesdevofteelopmentxturesofhaavegeneralbeen

130

10.2.TEXTURESYNTHESISANDTRANSFER

invented.Proceduralmodels[EMP+94]aresuitedfornaturaltextureslikewood
orstone.ParametricmodelsbasedontheMarkovRandomFieldmodel(e.g.[HF07])
areonlycapableofreproducingmainlystochastictexturesandareexpensiveto
evaluate.Ineithercasetheselectionofappropriateparametersmightbenon-
trivialandmanytexturescannotbereproducedusingproceduralmodels.There-
fore,researchersstartedtofocusonnon-parametricmodelsbasedonexample
textures[EL99,WL00].Theideaistogeneratealargerbutperceptuallysimilar
versionofasmalltexturesamplebyiterativelychoosingpixelsorpatchesfrom
thesamplewhich"fitwell"(intermsofaspecificmetric)intothealreadysynthe-
sizedpartoftheoutputtexture.
Whileapartfromavoidingrepetitionartifactsthegenerationoflargerversions
ofinputtexturesmightnotsoundthatusefulinitselfthesignificanceoftexture
synthesisformaterialeditingbecameapparentwiththeideaofconstrainedtexture
synthesis[Ash01,HJO+01].Inthiscaseconstraints,typicallygivenasimagesor
owfields(e.g.[KEBK05]),areusedtoguidethesynthesisprocessandthus
enablesomekindofusercontrolfortexturesynthesis.+Thequestionremainshow
togeneratetheseconstraints.Zhouetal.[ZDW05]presentedamethodwhich
usesconstraintgraph-cutsynthesistoallowtheinteractiveplacementofBTFs
onsurfaces.Thesynthesisisusedforseamlessblendingandnotforeditingthe
BTFitself.IntheworkofMertensetal.[MKC+06]amethodispresentedthat
transfersthetextureofascannedobjecttoarbitrarygeometrywhichthenactsas
constraint.the

131

C

HAPT132

ER1

0

.

R

ELTAEDANDC

ONCURRENTW

ORK

artP

III

eClosur

133

CHAPTER11

CONCLUSIONS

Figure11.1:Renderingaleatherdragonbasedalmostcompletelyondata-driven
hastechniques:beenscanned.TheThelightinghasmaterialsbeenonthecaptureddragonusingandathelightplaneprobehaveandbeenthemeasured,geometry
compressedandeditedbythetechniquespresentedinthisthesis.

Summary11.1

Thedigitalworksensorpresentedtechnologyinthiswhichthesisnowwasallodrivwentobycapturethegigdramaticabytesimproofvvisualementsdatain
inobjectsaneverandshortermaterialstime.withafidelityImage-basedandefdatafectiisvableenesstoalmostrepresentimthepossibletoappearanceachievofe

135

CHAPTER11.CONCLUSIONS

withpreviousmethodsbutitalsodemandsfornewtechniquestohandlethelarge
data.ofamountlessAlthoughindependentthetwfromodifeachferentotherpartstheofythisboththesisserveacanbesinglepurpose:comprehendedmakingmoretheor
practical.applicationofFromacomplexpersonalmeasuredpoint-of-vieappearancewtheadventrepresentationsoftheselikedata-drithevBTFentech-more
niquesinscenemodelingallowsartisticdilettantesliketheauthorofthisthesis
tofollocreatewsthealmostindividualphoto-realisticsummaryofimageseachlikofetheFiguretwo11.1parts:inonlyafewseconds.It

essionComprI:artPingThefirstsystem:partcoveredcompression.themostSincetheimportantrawcomponentmeasurementsofanyfromaimage-basedsinglematerialrender-
alonecanrequirethewholemainmemoryofatodayspersonalcomputerwith-
outeffectivedatacompressionthewholeapproachwouldbeinvain.Suchcom-
pressiontechniquesshouldnotonlyreducetherequiredmemorytomanageable
originaldimensionsdatafwhileastenoughpreservingastherequiredvisualforqualityinteractibutvealsoandallowhigh-qualitytoreconstructrenderingthe
applications.InChapter4wecomparedinthisrespectseveralcompressiontechniques
basedadaptivonelymatrixcomputedandtensormatrixfblocksactorization.offersWtheebestdiscoveredcompromisethatthefbetweenactorizationcompres-of
sionratio,reconstructionerrorandrun-timecosts.Inourexperimentswereduced
thestoragerequirementsofourexamplesfromaround2-3gigabytesdownto
10-20megabyteswhilepreservingahighvisualqualityandreconstructionperfor-
mance.Wealsoshowedthatrecentlyintroducedcompressiontechniquesbasedon
tensorrun-timefcostsactorizationareareordersofcurrentlymagnitudenotanhigheroptionforcomparedpracticaltomatrixapplicationsfactorizationsincethefor
thesamereconstructionerrorandcompressionratio.Therefore,theapplication
ofareaevenforhigherthesetechniquesdimensionalwilldatasetsberatherwherethecomputerfactorizationvisiontasksofandadditionalcompressionmodes
amortizesbutnotinteractiverenderingofmaterialappearance.
Inordertofurtherimprovetheperformanceofmatrixfactorizationbasedcom-
pressiontechniquesweintroducedinChapter5analgorithmwhichefficiently
computeslocalcoordinatesystemsforeachsampledsurfacepointoftheBTF
dataandtherebyimprovesthecorrelationbetweenindividualdatavectors.This
meansimprovedthatlesscorrelationdatahasresultstobeinastored.reducedOurrankmethodofthecanco-vbealsoariancematrixinterpretedwhichasa
monlygeneralusedmulti-viewassumptionsphoto-meliketricdiffusestereoreectance.techniquewhichdoesnotdependoncom-

136

11.2.FUTUREWORK

EditingII:artPThesecondpartofthisthesisdealtwithanotherimportantaspectwhichmightbe
notasobviousasdatacompressionbutisofalmostequalpracticalrelevance:edit-
ingofappearancedata.Sincemeasurementisanexpensiveprocessandinapracti-
calworkowrequirementscanchangefrequently,3Dmodelingartistsneedways
ofeditingthestructureandreectanceofthemeasuredmaterials.Forexamplein
oneapplicationthemeasuredleathermaterialshouldappearalittlemoreglossy,
whileinanotherscenariothecircularcolorpatternsofameasuredtextilematerial
shouldbesquareandsoon.ForthispurposewedevelopedtheBTF-Analogy
techniquewhichwaspresentedinChapter8.Itallowstotransfereditsmade
onasingleproxyimage,e.g.adepthmapofthematerial,tothewholedataset
bylearningcorrespondencesbetweenthelow-dimensionalproxy(thefeature-of-
interestmap)andthehigh-dimensionalBTF.Themethodwasmadeinteractiveby
exploitingstate-of-arttexturesynthesisalgorithms.
TheBTF-AnalogiesalsoformthebaseofmeaningfulBTFinterpolationpre-
sentedinChapter9whichallowstochangethereectancebehaviorofBTFsin
acompletelydata-drivenwaywhichmeanswithoutanysimplifyingassumptions
aboutthereectance,e.g.informofaparametricBRDFmodel.Togetherwith
aproceduralmodelforthematerialstructureacompletemodelofaparticular
materialclassbasedonrealmeasurementscanbeassembled.

orkWeFutur11.2

Inbypracticalreectancemodels,applicationstheproceduralcreationshadersofandmaterialstandardappearancetextures.isstillNevertheless,dominated
theniquesdemandpromiseforsolutionshigh-qualityforthemeasuredproductivityappearanceproblemisgroofwingComputerbecausetheseGraphicstech-as
anothermentionedjigsainwthepieceintroductionwhichhelpsofthisimprothesis.vingWtheehope,applicabilitythatthisofthesishighlyactsproductiherevase
representationsliketheBTFinpractice.Ofcourse,wearestillonlyatthebegin-
andningofeditingaaprocesswaitandanswering.manyopenresearchquestionsinthefieldBTFcompression

essionComprI:artPMostofthecurrentlyknowncompressiontechniquesforBTFshavebeenadapted
fromotherresearchfieldslikemachinelearningorimagecompression.Whatis

137

CHAPTER11.CONCLUSIONS

Figure11.2:ComparingarealBTFwithacompletelysyntheticmodel.What
componentsmakeamaterialappearrealistic?IstheBTFmorerealisticthanthe
model?synthetic

stillmissingisauniquepsycho-visualanalysisformaterialappearancecompa-
rable,e.g.tothepsycho-acousticanalysisknownfromaudiocompression.We
havetakenafirststeptowardsthisdirectionin[GMSK08]wherepsycho-visual
techniquesfromvideocompressionhavebeentransferredtoBTFcompression.
Inasimilardirectionpointsalsoanotherquestionwhichalreadyhasbeen
broughtupinourworkabouthybridmodelsforcar-paint[RMS+08]–howmany
realorimage-baseddataisneededandwhatpartsoftheappearancecanberepre-
sentedbyaparametricmodel?Thisaspecttouchesthequestionaboutthebuilding
blocksofmaterialappearance.Figure11.2showstwoimagesofablob-likeobject
whereoneimagewasrenderedwithameasuredmaterialwhiletheotherimage
usedacompletelysyntheticrepresentation.Sincethesyntheticmaterialmodelal-
lowscontrollingitspartsitispossibletoaddandleavecertainpartsofthematerial
representation.Thenitcanbedeterminedhowthesepartsaffecttheperceptionin
comparisontotherealreferencematerial.
Itisnotsuchabigsurprisethatmanyoftheopenquestionsinvisualdatacom-
pressionarerelatedtovisualperception,sincethesizeofourmodelsandscenesis
reachingacriticalsizewere"bruteforce"techniquesalonedonotsufficeanymore
andanin-depthunderstandingofwhatpartsofasceneareactuallyperceivedby
humansandwhichcanbeneglectedbecomesworthwhile.
Thesamecanthingcanbesaidaboutthelighttransportprocessesgoingonin
thematerial.Startingfromourworkaboutdata-drivenlocalcoordinatesystems
itwouldbeinterestingtoinvestigatehowrealgeometrycanbetradedforimage-

138

11.2.FUTUREWORK

basedmeasurementsandwhendotraditionalrepresentationslikedisplacement
mapsandBRDFssuffice.Howimportantisthesimulationofhigherorderlight
transportandinwhatcasesdowegetawaywithapproximations?Animportant
issueherewillbealsothetransitionbetweenscalessincemorethanfifteenyears
afterBeckerandMaxsseminalpaper[BM93]therestilldoesnotseemtoexista
satisfyinganswertothequestion:whatistheoptimalmulti-scalerepresentation?
Aninterestingstartingpointforfurtherresearchmightbetheintegrationofmea-
suredlighttransportlikeBTFsintohierarchicalpre-computedrepresentationsof
lighttransportlikethe+MeshlessHierarchicalLightTransportrecentlyintroduced
byLehtinenetal.[LZT08].

EditingII:artPThereisamultitudeofpossibledirectionsforfutureresearchinmaterialediting.
Anobviousextensionofourapproachwouldbetheintegrationofmodels
forproceduralothermodelsinterestingarematerialalreadyavclassesailable.likeInorderstone,towooddealorwithclothmaterialswherepoconsistingwerful
ofseveraldifferentsubstrates,e.g.withdifferentcolors,itwillbealsofruitfulto
combineourtechniquewiththeBTFselectionoperatorsintroducedin[KBD07].
Itwillalsobeinterestingtocompareourresultswithsimulateddataoreven
todatabaseincorporatewithoutthesimulatedneedformaterialsadditionaltoeincreasexpensitheveexpressimeasurements.venessofthematerial
Onthelongrunagenerativemodel,probablybasedinpartsonadatabase
ofmeasurements,whichwillallowtoefficientlycreatephoto-realisticandmulti-
scaleinstancesofmaterialsusinganintuitivesetofparameterswillbetheultimate
goal.

139

140

C

HAPTER1

1

.

C

ONCLUSIONS

[AB91]

[AP08]

[AS00]

[Ash01]

[BK07]

[Bli78]

[BM93]

[BN76]

[Bra03]

[CBCG02]

BIBLIOGRAPHY

E.H.AdelsonandJ.R.Bergen.Theplenopticfunctionandthe
elementsofearlyvision.M.LandyandJ.A.Movshon,(eds)Com-
putationalModelsofVisualProcessing,1991.

XispaceaoboeditAnpropagandFation.abioACMPellacini.Trans.GrAppprop:aph.,all-pairs27(3):1–9,2008.appearance-

Mmodel.ichaelJournalAshikhminofGrandaphicsPeterTools:ShirleyJGT.,An5(2):25–32,anisotropic2000.PhongBRDF

onMichaelInteractiveAshikhmin.3DGraphicsSynt,hesizingpagesnatural217–226,te2001.xtures.InSymposium

BrettW.BaderandTamaraG.Kolda.Matlabtensortoolbox,
2.2.ersionvhttp://csmr.ca.sandia.gov/~tgkolda/2007.January,TensorToolbox/

JamesSIGGRAPHF.Blinn.78,pagesSimulation286–292.ofAwrinkledCMsurfPress,aces.1978.InProceedingsof

bBumparryG.renderingBeckerandalgorithms.NelsonL.InMax.SIGGRAPHSmooth93:Prtransitionsoceedingsbetweenof
tecthe20thhniques,annualpagesconfer183–190,enceNeonwYComputerork,NY,grUSA,aphics1993.andAinterCM.active

JputeramesF.generatedBlinnandimages.MartinE.Commun.Newell.ACMTe,xtureand19(10):542–547,reectionin1976.com-

M.Brand.Fastonlinesvdrevisionsforlightweightrecommender
systems.InSIAMInternationalConferenceonDataMining(SDM),
2003.May

W-C.Chen,J-Y.Bouguet,M.H.Chu,andR.Grzeszczuk.Light
fieldmapping:Efficientrepresentationandhardwarerenderingof
surfacelightfields.ProceedingsofACMSIGGRAPH2002,2002.

141

[Com74][Coo84][CT81]

[CWH93]

[DG98]+00][DHT

[Dis98]

BIBLIOGRAPHY

[Com74]L.Comtet.AdvancedCombinatorics.Reidel,Dordrecht,1974.
[Coo84]RobertL.Cook.Shadetrees.SIGGRAPHComput.Graph.,
1984.18(3):223–231,[CT81]RobertL.CookandKennethE.Torrance.Areectancemodelfor
computergraphics.InSIGGRAPH81:Proceedingsofthe8than-
nualconferenceonComputergraphicsandinteractivetechniques,
pages307–316,NewYork,NY,USA,1981.ACMPress.
[CWH93]MichaelF.Cohen,JohnWallace,andPatHanrahan.Radiosityand
realisticimagesynthesis.AcademicPressProfessional,Inc.,San
1993.USA,CA,go,Die[DG98]P.DebevecandS.Gortler.Image-basedmodelingandrendering,
1998.[DHT+00]P.Debevec,T.Hawkins,C.Tchou,H.-P.Duiker,W.Sarokin,and
M.Sagar.Acquiringthereectancefieldofahumanface.Proceed-
ingsofACMSIGGRAPH2000,2000.
[Dis98]Jean-MichelDischler.Efficientlyrenderingmacrogeometricsur-
facestructuresusingbi-directionaltexturefunctions.InRendering
Techniques98.SpringerComputerScience,1998.
[DMM03]I.S.Dhillon,S.Mallela,andD.S.Modha.Information-
theoreticco-clustering.InProceedingsofTheNinthACM
SIGKDDInternationalConferenceonKnowledgeDiscoveryand
DataMining(KDD-2003),pages89–98,2003.
[DvGNK97]KristinJ.Dana,BramvanGinneken,ShreeK.Nayar,andJanJ.
Koenderink.Reectanceandtextureofreal-worldsurfaces.In
IEEEConferenceonComputerVisionandPatternRecognition,
1997.151–157,pages[EL99]AlexeiA.EfrosandThomasK.Leung.Texturesynthesisbynon-
parametricsampling.InProceedingsoftheInternationalConfer-
enceonComputerVision-Volume2,page1033.IEEEComputerSo-
1999.,ciety[EMP+94]DavidEbert,KentMusgrave,DarwynPeachey,KenPerlin,and
Worley.TexturingandModeling:AProceduralApproach.Aca-
demicPress,October1994.ISBN0-12-228760-6.

[DMM03]

142

BIBLIOGRAPHY

[FC89]

[FCGH08]

[FH04]

[GCHS05][GG91][GGSC96][GLD00][GMSK08]

[GTLL06]

R.T.FrankotandR.Chellappa.Amethodforenforcingintegrabil-
ityinshapefromshadingalgorithms.InB.K.P.HornandM.J.
Brooks,editors,ShapefromShading,pages89–122.MITPress,
1989.MA,Cambridge,J.Filip,M.J.Chantler,P.R.Green,andM.Haindl.Apsychophysi-
callyvalidatedmetricforbidirectionaltexturedatareduction.ACM
TransactionsonGraphics(ProceedingsofSIGGRAPHAsia2008),
2008.December27(5),J.FilipandM.Haindl.Non-linearreectancemodelforBidirec-
tionalTextureFunctionsynthesis.InJ.Kittler,M.Petrou,and
M.Nixon,editors,Proceedingsofthe17thIAPRInternationalCon-
ferenceonPatternRecognition,pages80–83,LosAlamitos,August
IEEE.2004.DanB.Goldman,BrianCurless,AaronHertzmann,andStevenM.
Seitz.Shapeandspatially-varyingbrdfsfromphotometricstereo.
InICCV,pages341–348,2005.
AllenGershoandRobertM.Gray.Vectorquantizationandsignal
compression.KluwerAcademicPublishers,Norwell,MA,USA,
1991.StevenJ.Gortler,RadekGrzeszczuk,RichardSzeliski,and
MichaelF.Cohen.Thelumigraph.ComputerGraphics,30(Annual
1996.Series):43–54,ConferenceG.Getz,E.Levine,andE.Domany.Coupledtwo-wayclustering
analysisofgenemicroarraydata.InProc.Natl.Acad.Sci.USA,
2000.12079–12084,pagesMichaelGuthe,GeroMueller,MartinSchneider,andReinhard
Klein.BTF-CIELab:aperceptualdifferencemeasureforqual-
ityassessmentandcompressionofBTFs.SubmittedtoComputer
GraphicsForum,2008.
GauravGarg,Eino-VilleTalvala,MarcLevoy,andHendrikP.A.
Lensch.Symmetricphotography:Exploitingdata-sparsenessinre-
ectancefields.InTomasAkenine-MöllerandWolfgangHeidrich,
editors,EurographicsWorkshop/SymposiumonRendering,pages
251–262,Nicosia,Cyprus,2006.EurographicsAssociation.

143

+06][GTR

[Hac99][HB95][HF03][HF07]A04][HF

[HJ86]+01][HJO

+99][HKL

[HWL05]

BIBLIOGRAPHY

J.Gu,C.Tu,R.Ramamoorthi,P.Belhumeur,W.Matusik,andS.K.
Nayar.Time-varyingSurfaceAppearance:Acquisition,Modeling,
andRendering.ACMTrans.onGraphics(alsoProc.ofACMSIG-
2006.Jul,GRAPH)WolfgangHackbusch.AsparsematrixarithmeticbasedonH-
matrices.PartI:IntroductiontoH-matrices.Computing,62:89–
1999.108,DavidJ.HeegerandJamesR.Bergen.Pyramid-basedtextureanaly-
sis/synthesis.InProceedingsofSIGGRAPH,pages229–238.ACM
1995.Press,M.HaindlandJ.Filip.FastBTFtexturemodelling.InM.Chantler,
editor,Texture2003.Proceedings,pages47–52,Edinburgh,Octo-
Press.IEEE2003.berM.HaindlandJ.Filip.Extremecompressionandmodelingofbidi-
rectionaltexturefunction.IEEETransactionsonPatternAnalysis
andMachineIntelligence,29(10):1859–1865,October2007.
M.Haindl,J.Filip,andM.Arnold.BTFimagespaceutmost
compressionandmodellingmethod.InJ.Kittler,M.Petrou,and
M.Nixon,editors,Proceedingsofthe17thIAPRInternationalCon-
ferenceonPatternRecognition,pages194–197,LosAlamitos,Au-
IEEE.2004.gustRogerA.HornandCharlesR.Johnson.Matrixanalysis.Cambridge
UniversityPress,NewYork,NY,USA,1986.
AaronHertzmann,CharlesE.Jacobs,NuriaOliver,BrianCurless,
andDavidH.Salesin.Imageanalogies.InEugeneFiume,editor,
SIGGRAPH2001,ComputerGraphicsProceedings,pages327–
340.ACMPress/ACMSIGGRAPH,2001.
KennethE.HoffIII,JohnKeyser,MingLin,DineshManocha,and
TimCulver.FastcomputationofgeneralizedVoronoidiagramsus-
inggraphicshardware.ComputerGraphics,33(AnnualConference
1999.Series):277–286,Pun-MoHo,Tien-TsinWong,andChi-SingLeung.Compressing
theillumination-adjustableimageswithprincipalcomponentanal-
ysis.IEEETransactionsonCircuitsandSystemsforVideoTech-
2005.15(3):355–364,,gnolo

144

BIBLIOGRAPHY

[IO06]HayleyN.IbenandJamesF.OBrien.Generatingsurfacecrackpat-
terns.InProceedingsoftheACMSIGGRAPH/EurographicsSym-
posiumonComputerAnimation,pages177–185,Sept2006.
[JMLH01]HenrikWannJensen,StephenR.Marschner,MarcLevoy,andPat
Hanrahan.Apracticalmodelforsubsurfacelighttransport.InSIG-
GRAPH01:Proceedingsofthe28thannualconferenceonCom-
putergraphicsandinteractivetechniques,pages511–518,New
York,NY,USA,2001.ACM.
[Jol86]I.T.Jolliffe.PrincipalComponentAnalysis.Springer-Verlag,1986.
[Kaj85]JamesT.Kajiya.Anisotropicreectionmodels.InSIGGRAPH85:
Proceedingsofthe12thannualconferenceonComputergraph-
icsandinteractivetechniques,pages15–21,NewYork,NY,USA,
CM.A1985.[Kaj86]JamesT.Kajiya.Therenderingequation.InProceedingsofSIG-
GRAPH,pages143–150.ACMPress,1986.
[KBD07]JanKautz,SolomonBoulos,andFrédoDurand.Interactiveedit-
ingandmodelingofbidirectionaltexturefunctions.ACMTrans.
2007.26(3):53,,aph.Gr[KCODL06]JohannesKopf,DanielCohen-Or,OliverDeussen,andDani
Lischinski.Recursivewangtilesforreal-timebluenoise.ACM
TransactionsonGraphics,25(3(Proc.SIGGRAPH2006)):509–
2006.518,[KEBK05]VivekKwatra,IrfanEssa,AaronBobick,andNipunKwatra.Tex-
tureoptimizationforexample-basedsynthesis.ACMTransactions
onGraphics,SIGGRAPH2005,pages795–802,August2005.
[KL97]NandakishoreKambhatlaandToddK.Leen.Dimensionreduction
bylocalprincipalcomponentanalysis.NeuralComput.,9(7):1493–
1997.1516,[KM99]JanKautzandMichaelMcCool.InteractiveRenderingwithArbi-
traryBRDFsusingSeparableApproximations.InTenthEurograph-
icsWorkshoponRendering,pages281–292,1999.
[KMBK03]MellisaL.Koudelka,SebastianMagda,PeterN.Belhumeur,and
DavidJ.Kriegman.Acquisition,compressionandsynthesisofbidi-
rectionaltexturefunctions.InTexture2003,2003.

145

[Leh07][LFTG97]

BIBLIOGRAPHY

[KR03]P.KostelecandD.Rockmore.Fftsontherotationgroup.Technical
Report03-11-060,SantaFeInstitutesWorkingPaperSeries,2003.
[Kuh55]HaroldW.Kuhn.Thehungarianmethodfortheassignmentprob-
lem.NavalResearchLogisticQuarterly,(2):83–97,1955.
[LBAD+06]JasonLawrence,AnerBen-Artzi,ChristopherDeCoro,Woj-
ciechMatusik,HanspeterPfister,RaviRamamoorthi,andSzymon
Rusinkiewicz.Inverseshadetreesfornon-parametricmaterialrep-
resentationandediting.ACMTransactionsonGraphics(Proc.SIG-
2006.July25(3),,GRAPH)[Leh07]JaakkoLehtinen.Aframeworkforprecomputedandcapturedlight
transport.ACMTrans.Graph.,26(4):13,2007.
[LFTG97]EricP.F.Lafortune,Sing-ChoongFoo,KennethE.Torrance,and
DonaldP.Greenberg.Non-linearapproximationofreectance
functions.InProceedingsofSIGGRAPH,pages117–126.ACM
Press/Addison-WesleyPublishingCo.,1997.
[LGC+05]H.Lensch,M.Gösele,Y.-Y.Chuang,T.Hawkins,S.Marschner,
W.Matusik,andG.Müller.Realisticmaterialsincomputergraph-
ics.InSiggraphCourses,2005.
[LGM07]HendrikLensch,MichaelGösele,andGeroMüller.Capturingre-
ectance-fromtheorytopractice.InEurographicsTutorials,2007.
[LH96]MarcLevoyandPatHanrahan.Lightfieldrendering.Computer
Graphics,30(AnnualConferenceSeries):31–42,1996.
[LH06]SylvainLefebvreandHuguesHoppe.Appearance-spacetexture
synthesis.ACMTrans.Graph.,25(3):541–548,2006.
[LHZ+04]XinguoLiu,YaohuaHu,JingdanZhang,XinTong,BainingGuo,
andHeung-YeungShum.SynthesisandRenderingofBidirectional
TextureFunctionsonArbitrarySurfaces.IEEETransactionson
VisualizationandComputerGraphics,10(3):278–289,2004.
[LKG+03]HendrikP.A.Lensch,J.Kautz,MichaelGoesele,WolfgangHei-
drich,andHans-PeterSeidel.Image-basedreconstructionofspatial
appearanceandgeometricdetail.ACMTransactionsonGraphics,
2003.2(22):234–257,146

+05][LGC[LGM07][LH96][LH06]+04][LHZ

+[LKG03]

BIBLIOGRAPHY

[LMV00]

[LS00]

YS01][L

+[LZT08]

[Mac67]

[MBK05]

[McA02]

+05][MCT

+06][MKC

LievenDeLathauwer,BartDeMoor,andJoosVandewalle.Onthe
bestrank-1andrank-(r1,r2,...,rn)approximationofhigher-order
tensors.SIAMJ.MatrixAnal.Appl.,21(4):1324–1342,2000.

DamatrixnielfD.Leeactorization.andH.InSebastianNIPS,pagesSeung.556–562,Algorithms2000.fornon-negative

XinguoLiu,YizhouYu,andHeung-YeungShum.Synthesizing
bidirectionaltexturefunctionsforreal-worldsurfaces.InProceed-
ingsofSIGGRAPH,pages97–106.ACMPress,2001.

JaakkoLehtinen,MatthiasZwicker,EmmanuelTurquin,Janne
Kmeshlessontkanen,hierarchicalFrédoDurand,representationFrançoisforlightSillion,andtransport.TimoACMAila.Trans.A
2008.27(3),,aph.Gr

J.B.MacQueen.Somemethodsforclassificationandanalysisof
multivariateobservations.InL.M.LeCamandJ.Neyman,editors,
Proc.ofthefifthBerkeleySymposiumonMathematicalStatistics
andProbability,volume1,pages281–297.UniversityofCalifornia
1967.Press,

G.Müller,G.H.Bendels,andR.Klein.Rapidsynchronousacqui-
sitionofgeometryandBTFforculturalheritageartefacts.InThe
6thInternationalSymposiumonVirtualReality,Archaeologyand
CulturalHeritage(VAST),pages13–20.EurographicsAssociation,
EurographicsAssociation,November2005.

Dapearvidance.McAllisterPhD.thesis,AUniGenerversityalizedofReprNorthesentCarolina,ationof2002.SurfaceAp-

Wan-ChunMa,Sung-HsiangChao,Yu-TingTseng,Yung-Yu
Chuang,Chun-FaChang,Bing-YuChen,andMingOuhyoung.
Level-of-detailrepresentationofbidirectionaltexturefunctionsfor
real-timerendering.InI3D05:Proceedingsofthe2005sympo-
siumonInteractive3Dgraphicsandgames,pages187–194,New
York,NY,USA,2005.ACM.

TomMertens,JanKautz,JiawenChen,PhilippeBekaert,andFrédo
Durand.Texturetransferusinggeometrycorrelation.InProceed-
ingsofEurographicsSymposiumonRendering,2006.

147

[MLH02][MMK03][MMK04a]

[MMK04b]+05][MMS[MPBM03]W03][MPD

W04][MPD

+02][MPN

[MRP98]

BIBLIOGRAPHY

D.McAllister,A.Lastra,andW.Heidrich.Efficientrenderingof
spatialbi-directionalreectancedistributionfunctions.Graphics
Hardware2002,2002.
GeroMüller,JanMeseth,andReinhardKlein.Compressionand
real-timeRenderingofMeasuredBTFsusinglocalPCA.InVision,
ModelingandVisualisation2003,pages271–280,November2003.
JanMeseth,GeroMüller,andReinhardKlein.Reectancefield
basedreal-time,high-qualityrenderingofbidirectionaltexture
functions.ComputersandGraphics,28(1):103–112,February
2004.GeroMüller,JanMeseth,andReinhardKlein.FastEnvironmental
LightingforLocal-PCAEncodedBTFs.InComputerGraphics
International2004(CGI2004),June2004.
G.Müller,J.Meseth,M.Sattler,R.Sarlette,andR.Klein.Ac-
quisition,synthesisandrenderingofbidirectionaltexturefunctions.
ComputerGraphicsForum,24(1):83–109,March2005.
WojciechMatusik,HanspeterPfister,MattBrand,andLeonard
McMillan.Adata-drivenreectancemodel.ACMTrans.Graph.,
2003.22(3):759–769,VincentMasselus,PieterPeers,PhilipDutré,andYvesD.Willems.
Relightingwith4dincidentlightfields.InSIGGRAPH03:ACM
SIGGRAPH2003Papers,pages613–620,NewYork,NY,USA,
CM.A2003.VincentMasselus,PieterPeers,PhilipDutré,andYvesD.Willems.
Smoothreconstructionandcompactrepresentationofreectance
functionsforimage-basedrelighting.InRenderingTechniques,
2004.287–298,pagesWojciechMatusik,HanspeterPfister,AddyNgan,PaulBeardsley,
RemoZiegler,andLeonardMcMillan.Image-based3dphotog-
raphyusingopacityhulls.InProceedingsofSIGGRAPH,pages
2002.Press,CMA427–437.GavinS.P.Miller,StevenM.Rubin,andDulcePonceleon.Lazy
decompressionofsurfacelightfieldsforprecomputedglobalillu-
mination.InProceedingsofEGRW98,pages281–292,1998.

148

BIBLIOGRAPHY

[MSK06][MSK07]

[MSRB07]

[MZD05][NBB04][NDM05]

[Nic65][NNJ05][NO77]

[PB96][PH04]

G.Müller,R.Sarlette,andR.Klein.Data-drivenlocalcoordinate
systemsforimage-basedrendering.ComputerGraphicsForum,
2006.September25(3),G.Müller,R.Sarlette,andR.Klein.Proceduraleditingofbidirec-
tionaltexturefunctions.InJ.KautzandS.Pattanaik,editors,Euro-
graphicsSymposiumonRendering2007.TheEurographicsAsso-
2007.Juneciation,DhruvMahajan,IraKemelmacherShlizerman,RaviRamamoor-
thi,andPeterBelhumeur.Atheoryoflocallylowdimensional
lighttransport.InSIGGRAPH07:ACMSIGGRAPH2007papers,
page62,NewYork,NY,USA,2007.ACM.
WojciechMatusik,MatthiasZwicker,andFrédoDurand.Texture
designusingasimplicialcomplexofmorphabletextures.ACM
Trans.Graph.,24(3):787–794,2005.
ShreeK.Nayar,PeterN.Belhumeur,andTerryE.Boult.Lighting
sensitivedisplay.ACMTrans.Graph.,23(4):963–979,2004.
AddyNgan,FrédoDurand,andWojciechMatusik.Experimental
analysisofbrdfmodels.InProceedingsoftheEurographicsSym-
posiumonRendering,pages117–226.EurographicsAssociation,
2005.F.E.Nicodemus.Directionalreectanceandemissivityofan
opaquesurface.AppliedOptics,4(7):767–,1965.
KoNishino,ShreeK.Nayar,andTonyJebara.Clusteredblockwise
pcaforrepresentingvisualdata.IEEETrans.PatternAnal.Mach.
2005.27(10):1675–1679,,Intell.F.E.NicodemusandOthers.GeometricalConsiderationsand
NomenclatureforReectance.USDept.ofCommerce,National
BureauofStandards:forsalebytheSupt.ofDocs.,USGovt.Print.
1977.f.,OfJ.E.ProctorandP.Y.Barnes.Nisthighaccuracyreference
reectometer-spectrophotometer.J.Res.Natl.Inst.Stand.Technol.,
1996.101(5):619–627,MattPharrandGregHumphreys.PhysicallyBasedRendering:
FromTheorytoImplementation.MorganKaufmann,2004.

149

[Pho75][PL07][POJ05]

[RM00]+08][RMSw98][RoTG97][R[Rus98]

[Sch94][SG92][Sha48][SKU08]

BIBLIOGRAPHY

BuiTuongPhong.Illuminationforcomputergeneratedpictures.
CommunicationsoftheACM,18(6):311–317,1975.
FabioPellaciniandJasonLawrence.Appwand:editingmea-
suredmaterialsusingappearance-drivenoptimization.ACMTrans.
2007.26(3):54,,aph.GrFábioPolicarpo,ManuelM.Oliveira,andaoL.D.CombaJo˙Real-
timereliefmappingonarbitrarypolygonalsurfaces.InI3D05:
Proceedingsofthe2005symposiumonInteractive3Dgraphicsand
games,pages155–162,NewYork,NY,USA,2005.ACM.
RoerdinkandMeijster.Thewatershedtransform:Definitions,al-
gorithmsandparallelizationstrategies.FUNDINF:FundamentaIn-
2000.41,,formaticaM.Rump,G.Müller,R.Sarlette,D.Koch,andR.Klein.Photo-
realisticrenderingofmetalliccarpaintfromimage-basedmeasure-
ments.ComputerGraphicsForum,27(2),2008.
SamRoweis.Emalgorithmsforpcaandspca.IninAdvances
inNeuralInformationProcessingSystems,pages626–632.MIT
1998.Press,HollyE.Rushmeier,GabrielTaubin,andAndréGuéziec.Applying
shapefromlightingvariationtobumpmapcapture.InProceedings
ofEGRW97,pages35–44.Springer-Verlag,1997.
SzymonRusinkiewicz.Anewchangeofvariablesforefficient
BRDFrepresentation.InG.DrettakisandN.Max,editors,Render-
ingTechniques98,pages11–22,NewYork,NY,1998.Springer
ien.WChristopheSchlick.Aninexpensivebrdfmodelforphysically-
basedrendering.Comput.Graph.Forum,13(3):233–246,1994.
ThomasW.SederbergandEugeneGreenwood.Aphysicallybased
approachto2-Dshapeblending.InProceedingsofSIGGRAPH,
volume26,pages25–34,1992.
ClaudeElwoodShannon.Amathematicaltheoryofcommunica-
tion.TheBellSystemTechnicalJournal,27,1948.
L.Szirmay-KalosandT.Umenhoffer.Displacementmappingon
theGPU-StateoftheArt.ComputerGraphicsForum,27(1),2008.

150

BIBLIOGRAPHY

[SOF]http://www.cs.dartmouth.edu/∼geelong/soft/.
[SSK03]M.Sattler,R.Sarlette,andR.Klein.Efficientandrealisticvisu-
alizationofcloth.ProceedingsoftheEurographicsSymposiumon
2003.,2003Rendering[Sta95]JosStam.Multiplescatteringasadiffusionprocess.InInProc.of
1995.41–50,pages,EGSR[SvBLD03]FrankSuykens,KarlvomBerge,AresLagae,andPhilipDutré.In-
teractiveRenderingofBidirectionalTextureFunctions.InEuro-
graphics2003,pages463–472,September2003.
[TCS06]MichaelGoeseleTongboChenandHans-PeterSeidel.Mesostruc-
turefromspecularity.InProceedingsofIEEEComputerSociety
ConferenceonComputerVisionandPatternRecognition,pages
2006.1825–1832,[TZL+02]XinTong,JingdanZhang,LigangLiu,XiWang,BainingGuo,and
Heung-YeungShum.Synthesisofbidirectionaltexturefunctionson
arbitrarysurfaces.InProceedingsofSIGGRAPH,pages665–672.
2002.Press,CMA[VT04]M.A.O.VasilescuandDemetriTerzopoulos.Tensortextures:Mul-
tilinearimage-basedrendering.InProceedingsofSIGGRAPH,Au-
2004.gust[WAA+00]DanielN.Wood,DanielI.Azuma,KenAldinger,BrianCurless,
TomDuchamp,DavidH.Salesin,andWernerStuetzle.Surface
lightfieldsfor3Dphotography.InProceedingsofSIGGRAPH,
2000.287–296,pages[War92]GregoryJ.Ward.Measuringandmodelinganisotropicreection.
InProceedingsofSIGGRAPH,pages265–272.ACMPress,1992.
[WAT92]StephenH.Westin,JamesArvo,andKennethE.Torrance.Pre-
dictingreectancefunctionsfromcomplexsurfaces.InJamesJ.
Thomas,editor,SIGGRAPH,pages255–264.ACM,1992.
[WHON97]Tien-TsinWong,Pheng-AnnHeng,Siu-HangOr,andWai-YinNg.
Image-basedrenderingwithcontrollableillumination.InProceed-
ingsofEGRW97,pages13–22.Springer-Verlag,1997.

151

+08][WHZ

[WL00]

[WL03]

+06][WMP

or96][W

+04][WTL

+05][WWS

+08][WXC

+05]W[ZD

BIBLIOGRAPHY

Li-YiWei,JianweiHan,KunZhou,HujunBao,BainingGuo,and
Heung-YeungShum.Inversetexturesynthesis.Proceedingsof
ACMSIGGRAPH2008,2008.

Li-YstructurediWeivandectorMarcLequantization.voy.FastIntePrxtureoceedingssynthesisofusingSIGGRAPHtree-,
pages479–488.ACMPress/Addison-WesleyPublishingCo.,2000.
Tien-TsinWongandChi-SingLeung.Compressionofillumination-
VideoadjustableTechnoloimages.gy(specialIEEETrissueonansactionsImagonCe-basedircuitsModelingand,SystemsRenderfor-
ingandAnimation),13(11):1107–1118,2003.

TimWeyrich,WojciechMatusik,HanspeterPfister,BerndBickel,
CraigDonner,ChienTu,JanetMcAndless,JinhoLee,AddyNgan,
HenrikWannJensen,andMarkusGross.Analysisofhumanfaces
usingameasurement-basedskinreectancemodel.ACMTrans.
2006.25(3):1013–1024,,aph.GrStevenWorley.Acellulartexturebasisfunction.InSIGGRAPH
96:Proceedingsofthe23rdannualconferenceonComputer
graphicsandinteractivetechniques,pages291–294,NewYork,
NY,USA,1996.ACMPress.

XiWang,XinTong,StephenLin,ShiminHu,BainingGuo,and
Heung-YeungShum.GeneralizedDisplacementMaps.pages227–
2004.233,

HongchengWang,QingWu,LinShi,YizhouYu,andNarendra
Ahuja.Out-of-coretensorapproximationofmulti-dimensionalma-
Ptricesapers,ofpagesvisualdata.527–535,InNewYSIGGRAPHork,NY,05:USA,ACM2005.ASIGGRAPHCM.2005

WQingang,Wandu,TYianizhouXia,Yu.ChunHierarchicalChen,Hsueh-YtensoriSeanapproximationLin,ofHongchengmulti-
ComputerdimensionalGrvisualaphics,data.14(1):186–199,IEEETr2008.ansactionsonVisualizationand

KShi,unZhou,BainingPengGuo,Du,andLifengHeung-YWang,eungYasuyukiShum.Matsushita,DecoratingJiaosurfacesying
withizationandbidirectionalComputertextureGraphicsfunctions.,IEEE11(5):519–528,Transactions2005.onVisual-

152

BIBLIOGRAPHY

+03][ZZV

YeungJingdanShum.Zhang,KunSynthesisZhou,ofLuizprogressiVelho,vely-vBainingariantteGuo,xturesand
trarypagessurf295–302,aces.InNewYSIGGRAPHork,NY,03:USA,ACM2003.ASIGGRAPHCM.2003

ork,Y

,NY

153

USA,

2003.

CM.A

Heung-arbi-on,saperP

154

B

I

B

L

I

O

G

R

A

P

H

Y

wingfolloThesources.nal

freely

DATA

S

OURavailabledatausedinthisthesishavebeentakenfrom

UTIA,DragonASModelCRPrague

http://ro.utia.cz/demos/drak/

Vcine1999St.PaulKitchenDebevLightecProbe

http://www.debevec.org/Probes/

cCampus1999PataulSunsetDebevecLightProbe

http://www.debevec.org/Probes/

155

CES-xtere

156

D

TAAS

OURCES

LISTOFPUBLICATIONS

M.RUMP,G.MÜLLER,R.SARLETTE,D.KOCH,ANDR.KLEIN.Photorealis-
ticrenderingofmetalliccarpaintfromimage-basedmeasurements.InComputer
GraphicsForum,27(2),2008.

G.MÜLLER,R.SARLETTE,ANDR.KLEIN.Proceduraleditingofbidirectional
texturefunctions.InEurographicsSymposiumonRendering2007,June2007.

G.MÜLLER,R.SARLETTE,ANDR.KLEIN.Data-drivenlocalcoordinatesys-
temsforimage-basedrendering.InComputerGraphicsForum,25(3),September
2006.

J.MESETH,G.MÜLLER,R.KLEIN,F.RÖDERANDM.ARNOLD.Verification
ofRenderingQualityfromMeasuredBTFs.InProceedingsofthe3rdSymposium
onAppliedPerceptioninGraphicsandVisualization,July2006.

G.MÜLLER,G.H.BENDELS,ANDR.KLEIN.Rapidsynchronousacquisition
ofposiumgeometryonVandirtualbtfforReality,culturalArchaeoloheritagegyandartefacts.CulturInalTheHerita6thge(VInternationalAST),13–20.Sym-
2005.embervNo

A.NICOLL,J.MESETH,G.MÜLLER,R.KLEIN.FractionalFourierTexture
Masks:GuidingNear-RegularTextureSynthesis.InComputerGraphicsForum,
2005.September24(3),

G.MÜLLER,J.MESETH,M.SATTLER,R.SARLETTE,ANDR.KLEIN.Ac-
quisition,synthesisandrenderingofbidirectionaltexturefunctions.InComputer
GraphicsForum,24(1):83–109,March2005.

Z.NAGY,G.MÜLLER,R.KLEIN.ClassificationforFourierVolumeRendering.
InPacificGraphics2004,October2004.

G.MÜLLER,J.MESETH,ANDR.KLEIN.FastEnvironmentalLightingfor
157

LISTOFPUBLICATIONS

Local-PCAEncodedBTFs.InComputerGraphicsInternational2004,June2004.

J.MESETH,G.MÜLLER,ANDR.KLEIN.Reectancefieldbasedreal-time,
high-qualityrenderingofbidirectionaltexturefunctions.InComputersandGraph-
2004.February28(1):103–112,,ics

G.MÜLLER,J.MESETH,ANDR.KLEIN.Compressionandreal-timeRendering
ofMeasuredBTFsusinglocalPCA.InVision,ModelingandVisualisation2003,
pages271–280,November2003.

158