New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Image Computation

by: Betty Kertzmann

Image Computation CS 510

Betty Kertzmann
GPA 3.51

J. Beveridge

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

J. Beveridge
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 38 page Class Notes was uploaded by Betty Kertzmann on Monday September 21, 2015. The Class Notes belongs to CS 510 at Colorado State University taught by J. Beveridge in Fall. Since its upload, it has received 23 views. For similar materials see /class/210169/cs-510-colorado-state-university in ComputerScienence at Colorado State University.

Similar to CS 510 at CSU

Popular in ComputerScienence


Reviews for Image Computation


Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/21/15
Nyquist Rm Announcements Reading Materials and its implications 0 Homew M are d o Remember tnrs course na 7 NEW furfuii credit cs 510 7 Wed day15 Lecture 11 m FWEVES Va Febmary16392009 r Vuu may submit HEIW an n 5 not 0 Readrng shouid be rndependenr e L is urmaenai un Fuuner transfurms is Eln h We mater r Painters El Web sites in ectu o Emaiit em 0 re er CS coiostate edu WM FF 0 How many ofyou nnrsnem ext iy drrecred e s su ementsyuurunuerstanmngr 0 Good news today We gene 5 ma apprcazrun or Founer transforms m a m a e W Fourier Transform The Eununuuus Fuuna39transfurm Spatial vs Frequency Fu fxcosZIuxr r sszyx Huw mg rs me spa rar dumam representa run7 Cammuaus m Negative Frequencies o u M someumes see the 1D Founer 7 0mm MUN sammes m N transform wrtn frequencres rangrng from 7W Huw mg rs merrequensy dumam representatrunv 0 W2 7 Cammuaus m 527iuxN suspzn Andmemsemerumauansfum r M an err2 sziuepevwequencvN Magnum srne2 uxN Tne Wu represemanuns are equivaiem Fm 3 r u 3 N4 2M 2M 7 Sameinmmmmn m 2m cos ersm r em 7 Nu n M N N e 0niagn uvv avdandvevevseivansmrmatmns m a m m a ham eW rnrurm auun m mum s 2D Fourier Transform v o So far we have looked only ar 1D signals o For 2D signals the generalization is I fxycus2rlux47rtsin2nuxvy equencies are now wordimensional ufrequvfreqmy mu Anew 2D sine waves ans iooks We you d expect rn 2D Note thatme frequencies don t naye to be equa rn the two drrnensrons m o meow 2D Discrete Fourier Transform o What nappened to the pounds on x amp y o How prg rs the drscrete 2D rrequency space 7 representatron our a e W 2D Frequency Space Remembermat sgtltla ex But my one 2 nu y e 777 mu 4 quotnoquot 2D Frequency Space cont o Srze of 2D Frequency representatron ONE mmensrun mustvary 7mm 4W2 El NZ WHHE Daey manevwmchi Wquot n e N NZ Zvaiues perrredueney N2 Same as the sduree spamai representatrun an o e or Showing Frequency Space 0 e We pint rrrdrn ewz m NZ rn pd n drrnensrdns Tne resuit rs symrneme apdunne ungrn and tneredre redundant tpiuta umpiex number sndu We sndu tne rnagnrtude 81 every prxer a p2 rnu ism p 0 To drspray a rrequency space We do the r iowmg rdrne the pnese rnrorn anon n s2 more are ersa Passihie ism bBD mu mum s momma ewi a mum The Nyquist Rate o Whathappmed to the frequencies aboveN7 Above N you have fewa39than one sample pa halfrcycle Themfurehgh freqummesluuk hkeluwerfrequen es x i i i Pi A l iquoti i i ltll l i i V V J v V NJej Thsls oaovery oao new A has m m no7 Hui moron GaulnSMHM Let s get practical Frequency Aliasing o Highfrequency information masquerading as low 39equency information is called aliasing 0 Before reducing image resolution o Lowpass lter the image 7 Remove high rreouehcies oerore they cause harm 0 Example 1000x1000 to 800x800 reduction 7 Nyquist rate or destiria ion is lower than source morontux can a mum LowPass Filtering Zero out h1g1 frequmcy Founer coefficimts h To luwrpass one image El 1 eonvemo frequency dumam I 2 discard all wines roiu gt mresh r 39 3 Cunvmbacktu spaiiai dumam 39 39 Braintux FourierAppIez ii mm Wasom 139 a uiisuiereaneasieiwayn u i A mure e ieieniwayn momma Gain a mum Cunvululiun is a pieeuisoi oi ihinos io eorhe Convolution for everypixel Think of H1is as a sliding dnt prndurt swam Guthpmuam Convolution II o Formally convolution is oilen aipressed as fltx gltxeTltrgltxe 0dr o ofcoorse we are dealing Wim finite discrete functions fx gx2 game an 1wa sum 5 mm LelGlr 421 LelGZl3l3l3 ThmFlquotGlEIEIEIEI ThmFrGan zm ThmFlquotG2gtl2343 ThenF2 G2gt143S3431 an A m o a 0 Why mtroduce convomnon new 0 Because rnumpmngtwo Founer transforms e u am 5 the convo vmg men mverse Fou er transforms m at me LowrPass Filter LUWrFass mar r muluply by a pulse m frequmcy wane a Cunvulve me image wnh me mvase Fuuner Lmnsfurm ar a pulse Sm ller m me as Trunmledsmc 1 a o a The Gibbs Phenomenon 39 gm 0 Thetruncated smc 5 no ongera pu se n frequency Space passes smaH amuunts ursurne mgh frequenmes passes acceptamefrequenmes n uneven amuums may create negatva vames m unusua mrcumstances Image Transformations Nawwe have me backguund m cunslda39 ample mags transfunmuuns There are always Wm cumpunmls Wm catnth W aaa mama mangldsml mnemmm gausaangausaan o a Image Reduciions i l Image Reducu ons 11 Image Reduciion III Anyume lhe largel image has alowa resuluum than lh Example reduce hum lelK tn BUUXXEIEI pixels a We is u Ocyclzspxel suurce Image prevent frequency allasmg by luwrpass Sekd om sauce pixel 14th I The quimxmam of mm B i l39amg m aim his is seine is u s cyakspixel 39 s Inyxancce canle mun Gaussan 7 mm mm rumgel is cwlssmsmehuxel Diem W a a mum a mom came mummies us a Cumulve sauce mugs with 45 may Sim women m mi ssquotwhu stmmSD a whim mm ms afm minim sum 7 nzmmnmdk We now e vao cwnvxummhmumlhe 5115mm m memes a mini while a a ow massmisms cm a m on Image Transiormaiion Whali T Smoothing with a 1 wewanno keep lhe image 1KX1K7 i 2 Limits to Gaussians This is why Every image pmeessing paekage ineludes prede ned 5x5 Gausaan nasks Other nasks yuu build yuurselr The Gausaan nask ltsalfls a discrete ampling era eonunuous 3131 3 A Gausaan 5131315 Willi signas belown a areluu mall in be ampled at pixel lnlawls 019m ng mi 4 my lmage wnh Gaussian Smoolhing a l n Genaally ml used fur upramphng39 an a s ow m unison Implications of Smoothing All mm 15 based un Lhexda ufrepresemmg Lhexmageas a sum ufsmewaves thslmllthuassumpuumsabsum m m wllxny m 7 Wm mm mm mm m mm was mm mm 7 Occmsmagg 194 m Mummy mmnymm m slgulwmmtmdum gm mm mum mmmh uysnnpummxm mm mm s m mm mm Emmy sxxxmm m Fuuneranalysls dues desmbe Lhelmntahuns quD cum8mm and therefure urmge rmmpulauun Implementing 5 Announcements Thin Lens Models 0 Does eyeryone have access to me dass eoogre groom c3510 Lecture 6 Intensity Image Formau39on February 2nd An new 2009 Tracers are due two Weeks from today nyzeamsrorrmn 7 e What anguages should expem omerrssuev oRay A My Wm M m Properties of Thin Lenses Fundamental Equau39on ofThin Lenses Properties part 2 o Forevery pomt ab on an rrnage prane Zf mm o The posruon Y Z can be ocaed drstance z bemnd me rrgmrocar Q carcurated by rrndrng me rmersecuon oftwo por L there was a perm m meworrd x Y aysmat conye by 2 Such that aH rays of hghtfrom X Y ZMHe FR s 09mm 7 One raygues hmugh he renrocar pumt strwes str Re the hm enS converge at a b z FL me rerrs ata by L and pmceeds parauer tn me up r axrs In a nu One ray go sfrum M2 araHeHume um F ZZ axrs mm 5 smkes me ens and 5 men re ected p thruughme enrucar purmu a nu Nora Pt quotnot oofm fmm optml am a Wenmew Swarm We Ray Tracing Thin Lens Huw du yuu du myuaung w Many mys urugm cunva39ge un every pixel 5 a pixel wine 15 mw me ayaage quhe ugm remmed alung many my n H 11 Me do we me neg se arenas Me lens new man when me new eemrmmymx Finding P XYZ Huw du yuu eumpme lans denemunsn Every my frum a smgle mags pmnlde e15 uward a smglepumlm Lhevmrld me Lhexmagepmnllu Lhelens shuunvm mys ome yardlem en n an Finding P cont These Wm de eded mys xmarsed at same pmnl m the vmrld All ems mys assunaled wnh ms pixel gu hm the surface quhe Ian 5 mm was pmnl Sn re my fmm eva39ylEns sun39aeepmnuuwammu pmnl one mennvev reed m and wage 15 mm I These are de eded accurdmg m the fundamen39zl equaums Th MO mm m u m WAO 5rd mg Fm 4m 5 m Shawn mrher fans 3 7 One thanth rmmruezlyum r Dunmex Mann mmeneemuesamesm ace anhesame 7 me smug on use We mean 7 WMHW Pamvnee lieemiemneeynem Sh amevexyxemnmmsaxv21 Newman ee enema ewe gem v memenm memenm we Previous Slide Illustrated ThIn Lens Model Revlew II The baswc a gonm mfor swmmaung amm ens therefore ooks ke m everv Wen ma paw m 3n warm he s m reevs srm mvmme revs 39am yers a paw Ray rraee ear rev Average remea My We em m on w more deta sezeer 5st of zens surface pa739I7I5 For every pixew Find povvt in an worm that is in Focus Inter5ert 2 rays wa surfaresj a through pr 27 through 72ft fp For every Wens surface point Shoot ray From Wens surface to point Average returned c rs b Review Illa 1 mpULE equatan of ens prane 2 Compute pest runs of tens pumts 3 Compute ne centercfrrnage prane A Furevery prxer 3 Compute prxerpesrtren o Compute ravfrern prxer to tens surface Compute ra from tens surface pernttnreugnfrentFP Compute ravfrern prxer tnreu n back FF to tens Compute ravfrern tens surface paraner to epnc axrs rntersectravs c 3 e frnu m focus perrt P Review quotlb 9 Furevery tens pumt L Compute rav R from Ltewaru P r Ray Trace R as rffrern prnnere carnera nAverage varues returned for 3H L s r store averaged varue m prxer But Wail What About the Straight Line Tmn Lens Q m WWW w m mm WWW w m Answer 0 Every rav from x Z tnat smkes tne tens converges at a or z o How about tne rav from x Y Z orectrv toward a or m tduesn t benm tpasses strargnttnruugn s rtatwavs m ne rmde oftne tensv Wail What about the apermre Held oI View x m we a m we Wm M m mm WWW w m Field ofView II o The caxcuxauon of x Y Z 5 theoreucaL and ma r sed to a cu ate n are mocked by the aperture 0 However the rays from some ens poms to x Y Z may be mocked These rays unmbute n n n mm the pwxe average Pmms nearme Edge urmemem urwew are therefure darker man was nearme rmde Discrete Sampling 5 510 Lecture 10 February 11 2009 Rewrite function as a sum or Cosine or sine waves Any 513131 mans nmrza39u ever nne range analsu be represented by an mime number er Sine Waves m 1 in Rewriting fx gx cosfxqgt azcosf2gtcligt2 Probiems May reqmre an mmte numberufterms rura umnuuus mncnun Must specwy an amphtude frequency and phase fur each an mm W Eliminating Phase Amg Mammy cosfx an acosfx sinfx Where 1 quot q 5 an a2 p2 1 cm Que em Therefore gx cusMx bA smfxa2 cus x A Sm x o Remammg probiems NEW a we as manyterms 2 perfrequency Need in specwy amphmde and frequencyfureach mm mm em Now Per Frequency o For any gryen frequency f1 we must cafcufafe ne fne arnpnfuqe offne Cosme and sr funcnons 0 cm rs rnfrnrfe x can be anymmg so We have to t the cosfnes and smes 0 EU the data a Ixrasym a freeware m mm m Represen 39 g Frequencies Our funcnon gx rs rnfrnrfery repeanng 0 Assume WLOG matthe umt of repennon rsf J 9mm awe o Omy cosrnes amp srnes an penoqsfnaf are rnfegers make sense omemrserswuufun frepea o Tne Cosme wnose penoq rs f rswnnen as m awake r o n generaf fne frequency that fepeata u frrnes over the mtefya 5 meen as 20527nx wnere u rs any mtegef m Hymn So to rewrite gx gx a cusanhsman a cus4nxb1 sm4nx For every rnfeger frequency u a e jgxcus2mxdx T lt gt b e g x sm2mdx m mm m Fourier Transform FmrmlltheFuuna39Lmnsfm mm les Fu j fxIcosZIwcrtstMdx Whareuxsanmlega39mthemnge frum lum Where a is used an mu a 21 mm wane Maerfuaxq m as aw The DC comp onent Whathappmswhmu 7 some 1 mm S Fun Ixxmzmermzmyx pfqu m 5 as m m ar Dc summary Mm rm n 5 may mm mm m war a Inverse Fourier Transform o What if I have Fufor all u and lwant to recreate the original function gx 0 Well sum it up for every u fxFu0052mxism2mxdu an mmnerM lmHaw IntuitionExample Time 0 Johns Hopkins Unlverslly e Signals Systems Control Wle nearlellsanloolvaexMml mar Wm Gailn 9mm Discrete Fourier Transform Problem an image isnol an analogue signal malvve can integate Therefore for o SultN Fu ixleosfxxj sm z 0 And the discrete lnvase transform is gallop ml 2 ml NW N N Where N ls one halthe dala elze fx are the dala values f0 mar unpalan Wm Discrete vs Continuous o Summation replaces integration I Division by N the number of discrete samples makes the unit of repitition 1 a For any signal continuous or discrete 7 cm ls called the Spatlal domalll e Fu ls called the frequency domalrl an anemones some Spatial vs Frequency Huw olg ls the spatlal oomalrl representatlom elven N samples ll ls slze N Huw olg ls the frequency oomalrl representanun Alulal ommleooeveles A cumplex vomoel 2 values pelllequency Agalnl the lEplEsEniailun ls olslze Nl Slrlse We have now a romaro allo lerErSE transfurmatlun the Wu rEprESErltatlElrlS are Equlvalent Exact salve l lollvallov Examsame slze There EXlSiS an o n log n aloollmvlol oom llavslollvallovs the FFT ave WEYSE Tl eoveleo lv 0557i SumEilmES lv CSSZEIEZEI mar Wm Mm 9mm The Nyquist Rate o What happened to the frequencies above N7 Abuve N you have few man one ample perhalfrcycle Therefure high frequencies look like luwer frequencies l 3 N l l l SalA A A Pl V l C NVl l l l v Thisisbadverybad owm Mom who o no a m Nun mar muttan some 2D Fourier Transform 0 So far we have looked only at 1D signals o For 2D signals the genenahzauon is my I I myensznnmyemnzman o Note that frequenmes are now twordAmensxonal frequvfreqmy o Every frequency uv has areal and an imaginary component m oemnm m Recursive Ray Tracing The General Idea Ray Tracing Intersections How an we see objects 7 Limieaves alight source bemees ermeneet and onto an reunam lm css 10 on itieaves alight source bemees urine abject then off amine and onto our nan January 25 2009 e on itieaves inert sauce bemees urine mice men mother mdanta mx nana We want to emulate this pmeess stamng at the cama39aur retina and Working backwards m rmpnkr ukn swim quotnewquot Computing Intersections Representing a Ray RayrturSurface intersection Calculations are Key 0 De ned by a point and a unit Y Tenement eemwaamnemneng mm Algorithms ueu to surface type RSLSU sane Pulygm o WhereEis the focal poin X gene smeesneny me we m ea am e and L is a pixel point Flrstpass General Matinemaues Lens Point 2 Second pass Highly opumlzeu Codes E quotL El mew We mm an We We mm quotnew Sphere Intersection Parametric Ray e Brute Force Sphere Intersection Brute Force Cnnsiiiera spherecentered atF with radiusr 0 Expand to see what is happening Let 2 IPePI a e a e LsUeP 0 e n e l e n e i Jen substitute 1 x x x TPeL Yielding a quadratic equation 07 T 07 Ter2 mar Giulia man swim me u nye y nr a e maempnnauknamglm quotnewquot Sphere Intersection Reduces to Quadratic Sphere Intersection III n A er multiplying nut expand and called s terms Cmde 5 huf 2 Th f ezzyuyezzxux722ms a52bsc0 mm 2 zx erzu uyku Where sei bt 25quot a n u ts aumt vectnr Sn u 2 u Lquot 1 2U T 4U Tye n Sn the equatinn may bewntten as s e b 72UT z 2 372UTsTTrr 0 CT27r2 sU T U 017 marmpnnauhn amsz mm an asquot am 3m sz Actual Sphere Intersection Points But Wait 39 SW 2 Names mu Ecghl ql zpl rgf s The pruceedmg ququ naturaHy frurn parameme m m quot 5 pmvmuily stnre39d appruach tn mterseetmg umeets sU T U 017 Mums Buttsttsmar 7 2 e U T U 0272 lsqummt Might there be a mare Ef cientan s Ye Cnmputethe actual pnsmnns alnng39he m fanhe smalleSt s sew WW mate smssmsm mews new 7 WWW pnsmve s 3mutupnes x mmg Eadmms Lets see it P39 e Pquot s39U 1mm marmpnnauhnamwzm quotmm an asquot am 3m sz Sphere Ray Intersection Faster Method Faster Method V3 2 Assume R is gwen 7 unit iength ray mreeuen 5 Need to cumpute v v 7ER dub ew dLst If d2 less than zero no intersection otherwise 0 E vdR mews Wm armum Euth r2 and I are atready cumputed s4 cumputedtuvcase aycummgtmmtucai pumt Test w r2 is greater m ezevz an an cm W tntersectmn a EvedR 1 subtvact muittphes Eaddttmns Anuther reference run this appruach s W E wgvawgscamathevvagvacmgbasmMmi marmwnauk 3m sz mm Intersect a Polygon Face Polygon Intersection II Fnrpnlygnnal objects there are two pans 7 Fmd pmnt nflntersectmn P on 1n n1te plane N39 L 5U d 1 n 7 Testlfpmntl lnsldepnygn xNUrNLd Generals uatmnfnra 1mem3D q axbyp 1170 N bid Therefore an xyzpmntP15 an aplane 1g N P7 e Where 82 ewe111 What gftkuuzen Nabc Cost mults 1 div 5 adds 1 neg mm Ginny GUI1 an sz Newman an sz quotNew Is the Point Inside the Polygon OddEven Parity Rule 39 Tmy fff f mwm o Tests whether a 20 point P is inside or my outside of a polygon 7 Stepl draw a rayfrom F39 in anydirection in me 7 Elna wzxpolmmJigmdmmakm o 1m New 7 Step 2 count new many boundaries are crossed one olmleisecllons Dlnslde ism Ska hrupmmsmrmm IEvenulmleisemmHSDUUlside 7 Map tn 2D ylarlz flan How 7 surlaces 7 ChaphulOK Ortl39mgmphln meme xy x1 my More xyeclalmd arid typic yfaxtermthndx amenquot GUI1 Minnow we 1 mm mm cw smm OddEven Illustrated OddEven Intersections Every polygon nas a set ofvemces Pl m w a At lnltlalllatl n store we set at edges ElP27Pl E2P37P2 Empwn To intersect ray R Wiln polygon F39 Find inleisecliun point lP between lay and plane Cieale iayslamng at 1R unhugunallu suilace nuimal Count mleiseclions between lay and buundaiies Dneenen doesn t malleil maemnmm an sz w we 1 my men Gui1 smm OddEven Intersections ll Key calculation ray to ray intersection 7 Nate that hath rays ave a free variable T lmensluns 2 a equatluns mm amquot am 3m sz s oNo this efficient 7 Elutlts eas 7 its general intersecting pulygun o ore ef cient methods for convex polygons les Wurks fur nunmunvex and self7 s M and for trian mm mm mm 3m sz Geometric Image Manipulau39on Image Manipulation Wenowmvemeoaekoomam moungm cunslderslmple Lawrpass FHtErmE suurce ge rmgetmnsfurmauu s Rem evgya v theruxsvmeaHhetavget Tharearealwayslvmcumpunmts Cauateme Eumarmtransfurmatmn on m mm armamemummgagerm Esahhshmmmappmg s manuang Lecture 12 m I Nahum mammaemtemdv mes February 18 2009 7 Pk mm wh mmw w s uvcem ooyea I Tms lecmre WAll remewslmple 2D Lmnsfurms e1 swme mtmduce sums nswan puwaful lenhmq vw pass mvwmumn sum22m tavget Image Transformations n39yabu Image Transformau39ons II The simplest set oruansrormaums areuanslaum roman and sale Thesemgemerare ned me MWth Lmnsf Smlamyuansfo ha I namx farm the u homo cumpulea wine later arm 5 veAdegeesuf 39eedum s are PH m FH 1H for Kano may Mala Yormton Tmmlmton were the Q homogeneous roommates Similaril amp Af ne Transformations These Bubs cumbmed mm une genene namx 391 b c X Hint diagonal v d e f y menus arenot 1 n Specifying Amne Transformations T Bream axunkn smthemamxm39hmugh Ifyuu wenfy une puml m the suurce mags and a ding pmnl m the Brgel image that yields Wm These hnmr equauuns Bubs asly sulved w m m 5 Wx Wx W em wanM emespen r w h n 1 1 equal and bud Enwaunns b x ax 5 Mews Buzz Tmsmamxduesmnre Wham Thmse umlem y Cakmmnnmbm A warm hm Mm mammwmnan m addmgm away 1 Emmy y r 0 r nasaeemosnnmmon shamanquot Emm nnmwg T y n Xx Hewmnyuuspenry39hunamm orune ual SDpmvldmgthreepmnlrlurpmnlcumespmdmces wn imw 339 one s en esanaf nemamx if 743442 specu39ve Solving A me coma Transformau39ons Perspective Matrix Tms Bubs subsumed m m sulve em The mepmeess wnhy39s sulves funian sawma We a a commas Allanauvely setup a sysLEm uflmmr equaums and sulve We En gm beyundju af ne transfunmuuns We En du any pawemve uansrennauen era glans m a glans Tharefure we En made ammageas aplane m wane and pm 31 n emu any emenmage va does she am um we newquot emean Purim m cmm Whydueselemmt3317 Huwmanypmmsareneededm wenfythumamx Solving c0111 Solving 111 Multiplle gel ndufthefmmun And Express me result as a systEm ufllnarethuns 9 1 mg by c n n n in we u x y 1 a V 9Wld yf w H U U n m 1 mm mm b ulxlyllnnnrlrmc Nowrernanbermalmeu39sv39sx39sampy39sareknovm V1 n n H X1 1 gm m d goupmeunlmovmlams A X h D D D gm 7m 0 v n n n x I e v agbyciggaifyig no X y no y n Vdgt9 yf g rhy V n n n X y H w h Perspective Image Transforms Solving IV Imui on Fmallylnvmme cms39anlrra o What does the following matrix do7 y l n n n in n n x l v loony 39 H Xi h gm 239 J n x y I n n n n 1 n H il a mu Nulethatsuchdecumpusluunsare x y H eleminevth n n n x y l xv mmmmm Intuitions x What is the result ofapplying the matrix above L VN Orientation ofrotations is from positive X toward positive Y gin All rotations are about the on More Intuitions o What will the following matrix do l 0 0 0 0 l l 71 l o More speci cally what will it do to the previous image Check Your Intuitions 0 What s going on here More Intuition Checking 0 Part ofwhat you are seeing is a scale effect pusmve terms in the bottom row create larger w values and therefore smalleruv values o Something much weirderis also going on what happens when y m 7 How an you int pret this geememeauyv lsn tthe perspective taansfem iineaev 0 So how do you select transform matrices Perspective Transform of 2D Planes Continue u abcx v d2fy w gh 11 u wvv w o The only practical way to specify an image transform is by providing four point correspondences Computing Transformations 0 Remember how to build a transformation from four point correspondences quot1 7 y 1 0 0 0 ma em a v 0 0 0 x y 1 exp em 5 2 X y 1 0 0 0 7x2 ryzuz V2 0 0 0 x2 2 1 exit em 11 a X ya 1 0 0 0 we in 2 Va 0 0 0 K ya 1 43 we u x y 1 0 0 0 ex eyu g v 0 0 0 x y 1 en eyv h Computing 00 011 0144 0144 0520 15250 152144 15294 n n 1 n n n n n n n n n n 1 n n n 144 1 n n n n n n n n n 144 1 1 7211725 152 n 1 n n 1 7231114 1 n n n 152 n 1 7 51m 152 144 1 n n 1 7231114 721222 n n n 152 144 1 714222 713536 More Computing Remember Me gamer M71 mom 0 11 yields 3274 0 0 Cross Correlation Lecture 16 March 2 2009 CrossrCorrelau39on and Rotation l The brute fume appmaehm malnng ennetaunn msmsmve in mtauunls to generate RlEmplalesal R diffa39em angles name whammy the am a Only anaa an e bulybrse 1r wu eenm guess me anen39aunn ynu eema apply nn1y nne tarnplale pa pixel lumuun ea ha ha 12ml mam annameramn dues u even new Image as Surface Vxew39henna geas FoeruYUW39 pmdlocatwn 3914 mkm ycmbe drlmglrnm39as 3914 110ml aim an in uenza din uhmn IEalm39zmkabe a Ezbmuas Pr 5 anagrams Every pmm an me quotrage amee has a daremmn er mmum ehange remember your muluwnate alumnus a a nagnmae er ehange m that dimman Image Edges Rola oanYee Cross Correlau39o Es maljng Edge Orientation Tu cumpulethedlrecnm anamagmaenrehange Make suretanplate 15 centeredunan edge 0 Problem nnages are not really conunuous cumputethe nagnmae arehange m any Wm nnhngnna1 e Mama as manath ms direcnunsand ml mate a Mm Emmmmdm chj x nzii l Ea PM esuna39esemx dybasedun gm mphng Cumpute39he nagnmae arehange m the x at Y direcnuns 7 ma mama manage mm 11 emnamaea 7 ma Lhaleaccumle e d1x lxyrlxely annaaa g my Xvwr wn a new a IxyrlxlyIxrlyrIxy comma annaa wnhmuge Thena tudeufchan emthermxlmal diremmmsthen 3 g Makes cunalaum msenauve m recauen esunaung demmuves fmmtvm wines is hghly em 2 2 e xraaeaamaanasmamanaa pmne 4 391 The mentahunufmamrml changexs W Accurate Edge Estimation Wewantm cumpulearahmlued fun mn m Pmaeamm am dy 11weravearesamplesatequusantpamts Samauelmerunrua expanaan nmtams ants Taylursenes Accurate 11 Accurate III Snluukanheequauunsfurlx h ndffxrh Somebestil maskis 401fmm xh xh39x7 X 7 x71 f f f ham 314mg y AMI fxhfx7f x mmmmm mm e As an exercise the b25112 maskis 1780371 X X X X 5 X frhfrh1hfr 1 fx1y8fxlvy78fx4vyKPH MFA 2f Anasulverurnx 3 quot 12 X 1 M1 4H1 2 M Stable Edges Ill Discussion Matching Of course mer are am new and mer are Cunelauunisthebaseiechmqueagamslwhichuther TheFuuner Tmnsfurmcunvms waualirmgesmlu re atedto W5 be OW above and irragerralnhmgalgunthmsarecumpared fnzqwzmttzsandpham Canweu theseturrutch X Inssmauvemuanslauu mtaumandsmle imagesn e We don I care w aH edges are mmuphed by a X cmmmmmmmmmmm constant 7 3237 nuancanrrmusramaam TheFum mem s M m SD mm quotrages o The Sobe Edge Masks 0 areidmuml suaretharfrequmnesandphases neappmanhlulhehumevmrk 1 o 1 a a 2 mmumuum mum e 2 o 2 O O 0 Add mh m I Canwelelliflvmimagesare simlla 7 o i i 2 i e ruammxyrmwugmmammaamass D thsscmusguudgsmhhrscdcduumy m x v Scaling Functions Shining functions ramplmlyJelus reeusen u funcnunsahesams pnnnples mu apply m 21 Ifwe sea1e a funmmn x we ge1 Kax Where as a cunmnl Fbumzvfax What dues Lhs sayv Slmllarly xfwe shma runenm j axwmdx 1 Faun2rfxi Kn me xnwwdx e mew Correlation in Fr uency Space Remanberthe de mhun ufcummluum hxfx gx Ifugxudu 39 Wigwam s magma y39 5 e T emask ngsassumed m mem zem uutsxde Ufa m sews s esmmreeuemysm mlemge hmmmeyem em SmceLhexmagesareZMULtrussrcunelah ms 39 13mm 15 quot3 almnslanexampleufcunvuluhun usesquot gammmxem Corr elau39on Theorem So Mosaing o The Founertransform ofthe crossrcorrelauonxs Fasnnahngvbuthuwduwe W 0 So how can we s mm 1 e sh hngrelahun Thephase difference ma 7 gnelvm p11ures39zkmby shmmg me man FDWMWJF FE 6 S en Wm ldmhml mges shmeebymmyn xs papmmmam me Dpud am Fs1sthe Fuuner msfurm mm Emmyquot Each pxdure cun39amsa pxece erme seene m mduded Gsxs39h Feunauansfuxmer x m39heu39her m e m cemexsx mm arse assma as the M Whyxs39hs mtaesune B amuse Musmng39 is me process ufsutnhmg mesemgemer Meroemm hemmeme F F mm enelargenma e FEM W MW39V Itreqmres ndmg me shm durbelweenthetvm WW W mges Example Mosaicing 11 Mosaicing III o How do weMosaic images 7 We could do crossconelati on but both images are large so thisis expensive 0 What will be the result Lfthe images are identical other than the shi an you sum e power at each phase across fr s uv you will nd that all the energy lies at single phase corresponding to the shi x y 7 Alternatively we couloltake the Fourier transform of hem and me complex conjugate of one and compute o What lfthey are similar but not iolentical Then most of the me phase Sm using power lies at a single phase so perform the same 39 calculation and then peak detection 0 Is this cheaper than crossconelation Fourier Methods Back to Correlation Similarity Transforms o Mosaicing involves matching a whole to a shi ed o I said that if two images are similar thequot Phase conelation 0 So we can compensate for image translation using the Whole says that the maximum phase value conesponols to thebest shimhemm Xavy o What is therelationship between theheight ofthe peak and the correlation score ofthe images under that shin e What ifwe want to nd a small template in a larger image o Can we compensate for o Will Fuuner matching wurk7 7 image mta ur Y2 0 Why urwiiymti o Parseval s theorem says that Ih1xdx Hfrdf 7 image scallng7 Y2 mem 011m types ofpmblems does Feme 0 So normalizing source imagesnormalizes frequency ace Perspemved smmumm matching work and the height of the peak is the conelation score 0 How By using the shift theorem again Romu39on gtTranslau39on Our gual tstc apptya ccmdnate hansrcnnahcntc the cngnat 21131 durramlmage such thata change m mtauunbecumssa change m hanstatt chv a y ccnvmmg mm Cartesan c unrdmales tc Fular cmdtnates 7 mm xdrmdrlzPolnComdmks crancmtmzn an ts dxsme damn sham and dc Are ants vecmn39mm dc any ta dc hunt m Polar Coordinates Canaan 336 w 0 Why convert into polar coordinates e Eemusea an tau nhec mes pul u2 nIyuH an 2su mfg mm d LU MESH m n cuur er angt quota mass 1V1 Emmcu 13918 ApplyFuuna39transfunnlupulanrmge nd 12 n22su 122 mmsh 2n n27nn 127 shttttndtstancecccrdtnatemusthezact 21 nztsn 131 22 shttt trnphes manuan Enean wane Polmcoovdmmz Imp s y m Image mmmplmg e m btlmtzm mm 01mm Scale Shifl Whattrcnetmagets saledrelauveluanutha ccnvattnagetchchtar ccmdtnates a s e e the that the sh thecnan nds shuts m hcth dtmenscns su yuu En match tnages that are hcth mtated and salad Limim on s We En unly natch mtated andUr scaled tnage IfWIZ Imow thapomrrhtzy an mmzd amtat scaladabadtt We En match translated tmages Dr mtated at salad tmages hut nct hcth Thene lsan mfunnalxlaauvelechmque furhandlmg snan changes m translauunmtahun at sale 7 m mam M Wang sass sha zwlyn c damn he magmas an mum and Reheatme nshd them nacth atheslwld mans ta quotwave Interpretation Trees 08510 Lecture 32 April 22 2009 Assignment 3 Any questions Any progress Relational Models 0 Q How would you nd a house in an image 7 lltnown components rooriwallsiwindow doors 7 lltnown relations roofabove walls windows in walls 7 No rigid geometric model 0 A Match a relational graph model 7 Nodes are components 7 Relations are edges 7 Problem reduces to subgrapn isomorpnism Ifyau 2 had c5440 much uflhzs may bE zmzlzar Relational Models Example Nodzs X Sky Type Region orFOA Properties Blue or Gray Large Roof Type Region or FOA Pr ps straignthe Boundary Uniform coloramp tenure Walls Type Region or FOA Props Uniform color Type Po ygon Door Type Polygon Circle Reunions gt Above 3 9 Inside a Level with or above Interpretation Tree Overview Use tree Search to nd amapping ofmodel features to image features which is geometrically consistent y A Model Image Locally Consistent Interpretation Trees 0 Interpretation trees map image features onto model 0 as to preserve constraints 7 To assign image feature l to model feature A l and A must be ottne same type and tneir unary teatures must match 7 lfl l5 asslgl led to A then 2 cannot be asslgl led to B unless o 2 is E are tne same type is match as abuve o in satisrytne binary cunstralntsfurAStEi Example of a Tree Image M d 1 Blue max denote amlgnmentx m do not Mlaw uther amlgnmenm Interpretation Trees cont 0 Not every image feature will belong to the model 0 Not every model feature will appear in the image rrors o The best match is the one with the most correspondences Generic Interpretation Tree Algorithm Part 1 0 Let Model be the list ofmodel features m1mn 0 Let Data be the list ofimage features d1dm 0 Let Interp be an initially empty list of modeldata pairs 0 Let UnaryPm dJ return true iff dJ meets mquots unary constrain s 0 Let BinaryPm dJlnterp return true iff the pair m d is consistent in erms 0 binary constraints with every pair 0 List operators emptyp destructive pop nondestructive append Generic Interpretation Tree Algorithm Part 2 lnterpTreeWodel Data lnterpH rr emptyvalode return Interp m po Model maxlist Interp a o ifUnaryPm d and BinaryPm d lnterp newlist lnterpTreerlo el Data appendm d lnterp ifsizenewlist gt sizemaxlist maxlist newlist newlist Inter Treewodel Data Interp ifsizenewlist gtsizemaxlistmaxlist newlrsr return newlist Questions 0 Should the recursive call in blue be lnterpTree Model removed Data appendam dylrrterp o What would the difference be7 c What is the role of the last recursive call in green 0 What would be the effect of removing it I Is this algorithm guaranteed to terminate o How ef cient is it Observations 0 Note the number ofcombinations tried worst case x 1 mm2 mquot complexity0mquot o This can be inverted if model is largerthan data this is rare The complexity is then On quot 0 Pruning based upon geometric constraints is critical More Observations 0 Eric Grimson has proven polynomial complexity in the average case if e Conslder only rotatlon and translatlon e The rnodel ls guaranteed to be present 7 No partlal syrnrnetrles o Tnls ls uunterrlntultlvely nard Must models naye syrnrnetnes 0 Otherwise complexity is exponential Branch amp Bound 0 One way to limit the search is branch amp boundquot 7 ea gurnent to lnterpTree tnat ls tne slze ofthe largest lnterpretatlon found so faralorlg any p tn 7 lfthe slze ofthe current lnterpretatlon plus tne slze ofthe alnlng unrnatcned model ls less tnan tne curr 0 Guaranteed neverto introduce an error 0 On average prunes search tree some 0 In the worst case no faster than previous algorithm BampB Algorithm tbeStSlZe 0 N0te that thls l5 global lr emptypModel return lnterpl slzetappendwodel ll39lterp lt oestslze return NlL popModell axlls lrlterpl ford ln Data dol lrUnaryPrndand Bll laryPUn extendedimatch appen stslze Maxbe5t5lze lf rn lll ltel p dmldl ll ltel p ed l l l reeModel Data extendedimatch lf5lZerlerl5tgt5lZernaxll5trnaxll5t newllst newllst lnterpTreetledel Data lnte p r l lr SlZel lerl5t gt SlZernaxll5t maxllst newllst l l l l Ullman s Algorithm CACM 77 o Create an nxm matrix C e a l Data ls conslstel ltwlth Models 7 lnltlallze c a uslng UnaryPUa o Propagate binary constraints 7 Foreyery olnary relatlon relAlBl o Data ls only Eunslsterltvvlth M lr lt ls cunslstent vyltn sorne Data that ls cunslstent vyltn Mb 7 l e tn l s an Entry cm such that cb l and am lstrue o Dtnervylsel setentry Cutu zero 0 Keep Propagating binary constraints until no change in C Ullman s Algorithm cont 0 Preprocess by propagating constraints as descnoed on preylous slde 0 Search as before except 7 A ereyery rnodeldata bll ldll lg update c and repropagate oonstralnts 0 Note that branch amp bound is consistentwith Ullman s algorithm Fourier Analysis and Sampling Lecture 10 February 9 2009 Announcements o Ray Tracers are due Thursday Last chancetu ask uuesiiurrs nemre it is uuel Rememberrlts due 81 WEIRM Elrl Thursday o Trivia question rwhat kind of animal is that mer in the CO arm a new Course Outline i image Generation m 2 Image Manipulation u 3 image Matching a Feature Matching can a new Goa mage Manipulalion o Rorauon amp Seale o Frlrenng amp reeonsrrueuon o Compression o Plans to plane projection o Image to image marelnng Today e will inrroduee some sampling meory background 2D Sampling Any repealing parrern an be ennslrueleu imm an innnlle numba39 no sine waves rm sewers 2D Fourier Spectrum Any signal ma 5 nmrzem ever a nile range En alsn be represemed by an minue numba39 nr sine waves ofrhz Mana rl Image can a new Why Sine waves are a guud represemaum furrepaled pauems as maaxaasmhams Distrelepixel pauems areregmar Heliummmwhiczncmibengvenmuge haisemmaas Anyumecumpressmn mama asamaam mes Humane ah a s e w Fourier Analysis a Magic y OKrmny39 xlbuuksrmkeisubscurebul Wearejust rewriting a fun mn x uvera nneiange cm s ewequot The Sine Wave L39 a Tms rmybea review immhigh sehaai but Phase Amplitude FV Fenud Frequency lqud o a The S39 9 Wave II a J h gxgcos c2 Simplifying Phase Phasedesmbes whee me eyeie Emssesthexax is quotMassesaaaahiissmwm am rmhuwmwm mud mums no ma e mam has him or 7 ma he moses an Phase seamsl aisa ear Any wave wnh phase 9 En he Expressed as mam M0500 smlx cm swearsquot Phase 11 Z cos6 22 cos26 6 sin2 Where as a mi mdtmnz rhmrhtz some mm ha been h zd by aidtzgnztz m a ewequot Fourier Transform V Ma39hEmaumlly me Fauna Lmnsfm m m u is Kurfx1caslmxran2mdx whee uxsa frequmcy Fu is me cumplexamphludeal that frequmcy and is me square mul DH Fu ean be armed mm rm and rrragnary parts an Magnum Ii 7 Iyxtamww can name Fourier Transform II memmmdeata equmcyxs Fu R uFu Thephaseata frequmcyxs tanquotu m s new MagPhase vs Reallm ag The re auun heme and magmtude a Re Energy and phase 5 Caneswanpmarcunversmn rm Rm an my a m w en me nmp ex Fuuner va ues a n ma am Nomu on Warning I Yuu WAll alsu seeLhEFuunertransfurmvmnenas F01 fx2 dx Ths xs eqmwlemjnemuse manta s menmy 2quot e cusZ my smZ m mu never useuns farm huweva How do we directly compare two images Image Matching Lecture 13 February 23 2009 Axlt148yltl l r B 8140 Z 2L4xyeBxy x y oh homahzed by Image area about 5 grey values per pixel B Are these mages the same7 Are they stmttam Consider Three Propelties of L1 Distance Cunstuertwu vecturspmnts xltwmyltmm constderthe foHowtng rob em 0mm Appmams L1 7 Qty Btock Dtstance Z ZAXyr any p x y Euchdean Dtstance x y PM the umque pomt quotcosest to k otheIpOHIS X7 X Y7 2 U Name For Stmphctty do thts m R a me wtth k 2 2 0 quot3 31 LZVEuchdean Dtstance AW395XVD x mpunam Less Cummun quot 2 7 E 40 07 Get used u the Mahatanuhts Dtstance mstancestmttanty msttncttun Mutua mmmam Z Z APW AXBPCVV 5 See the probtem yet quot gtlt R gtR y S R Corretatton D R x R gtR 22Axyea Examij zes8es33e Zr4874246 In Comparison Consider L2 14 PM the unique porn quotcosesr to K omerpom u 5mg Lz zeswmesyegwela 2e418e414m2n Best Nutas 2 a s 2 Guud Let s may a Game m new Avmlirtu the abquot Fm Game eRandam Expeckd m A ennn Jet s Nuv vve edvvedmmn awnmnaneva ue Punchhne Eurrda mnmeas a Dred mammy Change m 5 Outrofrplan Lneplane translation rotation eene content e rotation sea1e ehange Change m illumination Change m mixedrpxxels Change m gam stop Electron noise Lel x luck 1 u again Correlation 22Ahvy1 m xv 3 2 AW 205W 3 What IS the undayymg mode 7 Assumptions of Corr elation 2ltmmmmgt Ah Assumele syalswrylmeady memenneennhmsnn nnmmnnenanmnmm Thsmmmzessmsumlym n esmmsmnmem 115m organ Special Cases Correlation cont Any Wm mar functt ons wtthpoattve slopehave cunelauunl o y agromoolooe more Computing Correlation I Currelaum ls Semin39ve tn rmoooo r Any Wm mar funmuns wtth diffam y sighed slupes have cunelauun cl oo o t Note that adding a constant to a srpral ooesnot change its cunelauun to any other apral 5 m o Lamas acll um try no Mm sou lemon try c o no roommatevo o no mo Jedm ltomh nn lno vmrds cunelauunlssensiuve to anyaf ne or WWW AMM W o Aooooomooooo os send as oomoooo orooioooo pmjemvetmnsfmmahun A B 7 into goolo manor rtooyomoyootht as good a Asstms Pixels daomz w tie otter 1 no o o t t x x Correlationrsunoetineo iorslopeuon quot4 WWW 2 JD Z JD Computing Corr elation 11 For ZaTIrmEn Correlation Space aprals we En scale than Without chanpng thar correlation scores to Whyoorohoohe umlJeYEVh yulr meta hmzm nkmlg N2 Degress of Freedom mwmmlwmg Mm mm o is rt really N72 degrees of freedom o rotooooomeootoo mmamlmgh mollmotnoooaor immoraler o oomotoooaooo to o What about 2D pornts then 5 mo 39l m nnwnnwlmmmn7n mt ammommmmooomoaoo mm W mm m Morrowmoooooooooooroarooocooooooom mommaorooooooammtomtoooooo Grvesnse to Correlation Space mnmmmu mm oommo magnoooooooooo Correlation Space ll o Subtracting mean rtran Correlation Space 111 v a 0 mmmm 5 mmxyememwmmm Mme o enth one rproject onto sphere 0 Correlation 5 d1 angle belwem vedurs pmms a My my E4xw25xy 24xy xy e Wee Axv xy m anm Nemsh zld huxchssx e mcmehcnnsyace mm comma


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Allison Fischer University of Alabama

"I signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I LOVE StudySoup!"

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.