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


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

Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 53 page Class Notes was uploaded by Betty Kertzmann on Tuesday September 22, 2015. The Class Notes belongs to CS 510 at Colorado State University taught by Staff in Fall. Since its upload, it has received 25 views. For similar materials see /class/210196/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/22/15
Recent Advances in Object Recognition CS 510 Lecture 29 April 15 2008 create an lmage Willi a f Puwwnsample by a 1mm Diziu return a u Tutal rust ur pyramld unstructlun lunvulutlunampduwnsample l4cunvulutlun ampduwnsample i g Tutal custlt 1 5 unvulutlun amp duwnsample w Nate ltls Dsslble tu havelntermedlate a es Scale Space 1 Create an image pyramld by Cunvulvlngcl lmage b 3113 in images Wl nin s 7 am unlyduwnsamplewhenc2 5 Difference of Gaussians DOG o A DifferenceOf Gaussians DOG function is an impulse lter constructed by subtracting two Gaussians with different 0 s in a ilwun Examples Cal Tech Data Set 0 Large set of images collected from the web 7 Every lmage contall ls a Sll lgle labeled oblect 7 Some riot all have backgrounds e 101 oblect categories 7 Some manlpulated to contall l a Sll lgle View 0 Goal label images given a training set e34 Alrplanes torcyles Spotted cats Fergus et al 2003 Fergus et al cont Variations o The rst reat resuits on he Cat Tech data set were 0 Atgorr hrh o Bag ofWordsquot Csurka et al Sivic et al by ergus eronaamp2r serrhah cpros 7 Testtng 7 momma 5 rem n5 7 Th dEsEnp Dn herers shghtiystmpimed raetFoAhumrma e Fur eyery FDA and caieguvyA eumpme PAF Th Worm 7 UsmgiheparameievsieamedvaM WE Fuvevevyumeciciass EnvactFOk mma Hramma mags 7 computers INAx vrSPAFimaHFOAsF Use PCA Etgenspaces in cumpvess Wage ehrps SEW m mm My crass Ciusievtmage chtpsmiucaiegunes EM Accur Fuvevevyume iciass eumpute anestanmudei 7 P AA X V SMsihepmbabtmvihainbiedciasschasanFOAM caneemyAatpnsrtrnnwmuscares 7 Perrmts otherctustehhg approaches IE 9 hearesth r hbur o Bayesian appro al aches FeiFei et al Holub et acy 7 am sputteu cats am arrptahesr 96 Muturcycie faces 92 7 Extends Fergus by butidtng Bayesrah hetworke Wi h exphctt Spattai reiattons among FOA categon StrengthsNVeaknesses of FDA approach Does this apply to o Strengths Assignment 3 FInd all Interest pomts irreievant Wage mrrerehces rghureu 3 7 Reiattveiy strung perfurm NEE Em naturai Wages 0 Weak 7 ObjectrKcuntExt are rhmstrhgurshame 7 Unabie tn incahze iabeied mute ts wrthrh a see 7 Susce tabie tn smaH da se ect qurr mng mhe uniy amen m yum data set w grassrrem eats 7 supewrseu iEarmng paramgm s are cais then if yuu uuh t attend tn tt yuu H heyerhhu rt hterest pomts on both targeter and tots or others or v n mu my s mmx m mx xxx xxxr but don t over threshold m mm Missed one s hm Mqu uni nu m m we at ma New topic Stereo o The ability to mfec 3D structure and distance from two or m ovalapping images takm simultaneously from diffecehtmwpomts Are them Stereo imagex Dexcribe the wewpomrx Scenarios o Most Common papmdicular opticai axes o Also Common Convaging opticai axes o More Common than you mightthmk arbitrary axes Two SubProblems o Image Matching correspondence identifying which points in image 1 match which points in image 2 hcta hctaii points in image 1 match anything in image 2 Why not7 thc hctaiimatchmgpcmts Enbe fuund 0 Reconstruction Given pcmt matchcs deterrmne thequot 3D pcsmch Requires mahgmatmhomphcit Dr cxphcit Image Matching 0 Find common some points in two images Occiusicm incompictc uvalap ufvisual elds Pctmtiaiiy stmhg pamcctivc effects 0 Gmaal Methods Cunelauun based Cmsscmdau mymxci inle imag tchghtimagc Epipnlaz geamz xycmcmsixmnihsseuuh Fmtucc based Exixactpainis edges imc etc mdmatchthzm acmssimage Reconstruction as Triangulation 0 Assume that the positions and baselines othe camaas are known hascimc I Rt Timhf Ry xtb17 Txyf Solve for T s compute coordinate of oint Q In t thiS overcanstramed7 Epipolar Geometry o For anypolnt ln image 1 there ls a hne ofpolnts ln image 2 such that lts match if one exlsts must he on that hne a o Thls ls because there ls aplane deflned by the two focal polnts and the polnt ln lmage l The scene polnt must he ln thls plane a o Also the matchlng polnt ln lmage 2 must he ln thls plane Why Epipolar cont o slnce the lntersectlon oftwo planes ls a hne there ls a llne ln image 2 on whlch the matchlng polnt must he Thls ls called the eplpolarltne o Ifyou lmow the Vrp s and prp s ofboLh cameras you can compute the eplpolar llne for any polnt ln lmage1 If axes are pamllel and Bzn then eplpolar llnes are smnlmes o The EssentlalMatrlx E and Fundamental Matnx F ow yo p te eplpolar geometry wthouleowlng u to Com u the camera parameters o pnon Getting Formal about Stereo Do norponlc about the rim Nstldec my god lSmt ta oseyou to termx amp cameptx ln caseyou go to a yelon conference Eplpular Llne Basic Equations P RP s T lRelatlon between 3D ylews ofpolntP T X P 2 Normal to eplpolarplane T P s T Tgtlt P 0 3 Planarlty constralnt R PT Tgtlt P 0 4Rewnte of3uslng l A Clever Equation You can rewnte a cross product as dotproduct so 2351 Where o sr Ty T 0 sTl on a o More Equations R P ISP 0 5 Substltute dot for cross ln4 PRTRSP 0 o Applytranspose equlvalency PRTEP0 7 LetRsE E ls called the Essentlal Matrlx by the stereo communltygt ofrank 2 because 5 ls rank 2 and shows a hnear relatlonshlp between theprolectlons ofpolnts ln two images Orin 2D 8 Defmmon ofperspecme 9 same 10 rewme of7w1Lh 8 11 drop nonrzao consan Back to Epipolar o So E 15 a lmearrelauon bemWeen p and o u Ep where u 15 the hue ofpomts m R that might match pomtp Fureveryxmagepumlp mmumebmw mm assume almgthathne o E can be calculated from 8 mage co espondmces Wh n uwmany DOF7 Huwmanycunsummsper cumewundmm Stereo Practicum o The largerthe basebne the more the paspectwe dxstomon Thehardennslumalnhpmnls o The smaller mebasebne Lhe smallerme angle between P e mgher Lhe reconstmctxon aror Emrsalwaysmgqestmz Stereo CS 510 Lecture 30 April 20 2009 Update Assn 2 Mostly graded 2 of you have emalls from me 1 2 3 Programstested on Alrplane amptemplate5 Chlmpanzee amptemplate5 New one sllgh ly house example Airplane Templates TIE3 Airplane Result Chimpanzee example New topic Stereo lstance from W 0 or m o The ability to infer 3D structure and more overlapplng images taken simultaneously fr New House Example dlfferentvlewpoln New House Templates 5 Are these stereo lmagex Desmbe the vtewpomts Scenarios Two SubProblems Image Matching 0 Most common peipendicular optical axes 0 Image Matching conespondence 0 Find common scene points in two images tdmufymg which points in image 1 match which points in image 7 o usion 1 e lncompleteoveilap ufvlsual elds note not all points in image 1 match anylhmgm image 2 Why pumm a y gm p spewve mm o Also common conver in tical axes 0 7 o G lMeth g g Op 7 Note not all matchingpoints Enbefuund em 0 S Camelauunb ed cmseemeiite my pixei mietimge ta hgtimige 0 Reconstruction Epipnlar geomeayemeohsoohthisseoeh o More common than you mightthink arbitrary axes 7 Given pointnnatches oetenminetheu 31 position peamrebased e s tnangulation implicit Dr explicit Exkanpmms edges lines etc andmntchthzm ieiossimige Reconstruction as Triangulation o Assume thatthe positions andbasellnes othe cameras are lmown Ri Tirityitf amp ohm leof Solve forT s compute coordinate f p oint Q Isn t thlS avemanxtmmed t baseline Epipolar Geometry o For anypoint in image 1 there is a line otpoints in image 2 such that its match If one exlsts must lie on that line 1 o Thls is because there is a plane deflned by the two focal points and the point in image 1 The scene point must lie in this plane mi 7 o Also the matching point in imagez must lie in this plane Why Epipolar cont o since the intersection oftwo planes is a line there is a line ch the matching point must lie Thls is tine in image 2 on Whl called the eplpala l o The Essential Matrix 1 an gt allo u to compute epip olar geometry without knowing e ca mmeters aprtart w yo meia pa d ist ofboth cameras you can epipolar line for anypoint in image 1 lel and EFU then epipular lines are scan lines d Fundamental Matrix F Getting Formal about Stereo Do notponic about the near leidex my goot 15145 ta apoxe you to term dc canceptx in case yauga to o WSKOVK conference Basic Equations Py RP 7 T 1 Relation between 3 VIEWS ofpointP T X P 2 Normal to epipolar plane T Pier mine 3 Plananty constraint R PyT Tgtlt P 0 4Rewrlte of3 using 1 A Clever Equation You can rewrite a cross product as dot product so TgtltP7SP where 0 or Ty T 0 on on a o More Equations R Py Isg 0 5 sllbstltute clot for cross lh 4 Png 0 6 Apply transpose equwalmcy PRTEB0 7LetRsE E ls called the Essehtlal Mamx by the stereo commuhltygt otlahk 2 because 5 ls lahk z and shows a llhear relatlonshlp between the pmlectlorls otpomts lh two lmages Backto Epipolar o So E ls a llnearrelatlon between p and p o u Ep whae ll ls the llhe ofpolnts lh R that mlght match p 0th p o Ifyou know E Eel eva39y lmage palhtp calculate the hm allyclasscalelate alaagtlaellne o E can be calculated from 8 Image correspondences Why 37 Huwmany DOF7 Huwmany E nslmnls pa E n39esp ndence397 Stereo Practicum o The largerthebasellhe the more the perspectlvedlstomorl heh ardenns tn matchpumts o The smallerthe basellhe the smaller the angle between P and pm the hlgaet the reconstructlon elm Enulsalwayshlghestlhz Recent Advances in Object Recognition CS 510 Lecture 28 April 13 2008 Review FOA A focus ofattention window marks an image feature that i Specifies a iocation and a scaie 2 Can be repeatediv identified 3 Contain informa ion 7 But how do we use them to recognize objects Review D06 0 Di erenceof Gaussians approach to E 5 er 3 3 er LO a u a 2 LDWE recommends 3 images per uctave 2 Es imate DOG responses ov subtracting iavers t Higniv errisient 3 Extract iocai extrema DoG Refinements Pusitiuns or extrema are a At nign ieveis ottne pvramid everv pixei represents a iaree numiaer pt muvce pixeis sesuppixeienersareimpertart Seaie measured in Mt octaves is eoarse Refine extrema positions and DDG vaiues by fitting a He ouadran runetion The 3x3 neignoornood around an extrema nas27vaiues it must he ioeaiiv paraooiie because its an extremum Atvsquadvaticiunctiun my terms so it can he ttu tne ioeai Wm We o bes cx vquot dx vs The suopixei position ottne extrema istne point wnere tms tunetion is maximai Corners amp DoG extrema o Lines and bars in images tend to create nign DOG responses o The positions orextrema aiong tnese reatures are determined ov noise and tnererore not staoie Corners amp D06 0 Solution DoG extrema should be comers 7 Compute edge direc ions dx amp dv in Window around ex remum s Compute tne eigenvectors ofthe derivative covariance matrix s Exciude extrema Whose smaiier eigenvaiue is oeiow atnresnoid Examples Alternative Approach Entropy Cal Tech Data Set 0 Erltropy ls a measure orurllrorrnlty 0 Large set ofimages collected 39om the web a H rleplxlluglplx Every lrhage cohtalrls a slrlgle labeled oblect 0 A good attenth Wl dOW l5 7 Some rlot all have backgrounds l0l oblectcategorles Urllfurm Wlthlrl thE erl EEEEI Some marllpulated to corltalrl a slrlgle VleW duw mes rlEIrlruerEIrm lrme erleew ls maee larger 0 Kadlr amp Brady deflrle a sallerlce measure based oh the derlvatlve ofH Wlth respect to scale Has adyucates because meery ls 53 0 Goal label images given a training set DEIESrl t seem te WDM as well lrl practlce Cal Tech Examples Fergus et al 2003 Fergus et al cont 0 The flrst real results oh the Cal Tech data set were 0 Algorlthrh by Fergus Perorla amp leserrnarl cpros Testlrlg The eeserlptlerl here ls sllghtly slmpllrlee Emael FOAtlum lmage rereyeryroAlane calegulyA cumpule arr Thar 5 90 th UsnglheparametersleamedvaM WW Fuveveryublecl elass e I EmachOAstrum alllralnlnglmages Camp e c EMA X y sPAFlnrallFOASF Us peltlelgsnsm m was We all Seem m my era s Cluslevlmage EhlpslnlucalegurlESEW Accuracy rereyer ubleclclass cum me Be eslan meeel a a a a m y y s WeWallyymmclassless roAm e m spam ram 9M Wales 96quot tram 9 calegnNAal Pnsllnrl maneseale s Muturcytle Momrcyles Airplanes spotted cats Variations o Bag ofWordsquot Csurka et al Sivic et al 7 tgnores soatrat retatrons 7 Permtts o nerotostenng approacnes I E g nearest net 0 Bayesian approaches FeiFei et al Holub et al 7 Extends Fergus by oortorng Bayestan networks wrtn exphctt soatrat retatrons among FOA StrengthsNVeaknesses of FDA approach o Strengtns trretevant rrnage orrrerences tgnured 7 Retattvety strung perfurmance on naturat rrnages Weaknesses Object r3 untext are rnorstrngorsnaote unaote to tocatrze taoeteo ootects thtn a scene susceptaote to smaH data set errect oven tmng tune uniyumeds m yum data set w gvass eids are eats tnen gvass eats supervrseo tearnrng oaraorgrn tfyuu dun tanend to tt yuu H neverftnd tt Review Canny Edges Point Matching Created by a threestep algorithm 1 Convolutions Gaussian amp Sobel CS 510 2 Directional nonmaximal suppression Lecture 31 3 Twothreshold hysteresis filtering April 20th 2009 39Createsedgesthat Fm Thin QLBLQj QEG 9 39 Linked Seai May correspond to scene structure Review Harris Corners Why Match Features c To ignore irrelevant data o Create 2x2 covariance Backgrounds matrix of local edge Meaningless variation among instances orientations o Eg color of car whether pickup is covered Variations in illumination 0 Solve for the two c To accommodate changes In vrewpornt eigenvalues lnsensrtlve to classes of transformations 0 If the smaller 0 Depends on the feature extraction and matching techniques eigenvalue is larger 0 Defining the class of transformation is critical to the success of any feature matching system c Underlying tradeoff Higher level features gtless data simpler combinatorics Higherlevel features gt greater chance for error in feature extraction than a threshold then the center of the window is a corner Simple Example Matching Points Feature Matching o Edges amp Corners can both be viewed as interesting 0 Correspondence problems 2D POlntS in an image One to one One to many Many to many 0 Geometric Transformations o It might be useful to match a set of edgescorners to SimiIarity Affine perspective pomts 39 3 ObJeCt mOde39 0 Noise missing and extraneous features Creates a correspondence problem which feature in image A matches which feature in image B MatCh metrlCS For individual feature pairs 0 Can any point match any point Forfeature sets 0 Geometric error measures 0 Similar but different from correlating edge maps Point Matching Examples Simple I 0 39 0 039 0 o 0 0 39 o quot Example 1 Example 2 Simplified Hausdorff Matching c To match a set of points A to a set of points in an image B e forevery pixel in B compute distance to nearest edgecornercall tnis irnage D e Make oinaryternpiate from points in A o How does this compare to crosscorrelation o What transformations does it admit The Directed Hausdorff Metric A distance measure between two sets of points 0 Given two sets of points A all qm B b1b2bn a2 0 The Hausdorffmetric Is h AB MAX MIN 1 e 1 a e A b e B o In other words it is the maximum distance 39om any point in Ato its nearest point In B e Wnat class oftransforrnations does tnis support7 Hausdorff cont 0 Note the directed Hausdorffmetn39c is non symmetric e Goodforcomparingmodelsto images e Goodforcomparing subimagestoimages e Less good forcompanng two images 0 A symmetric version is de ned as HAB MAXhABhBA Robust Hausdorff o The Hausdorffmetn39c is highly sensitive to noise 7 One outlier point in Set AWiH ruin the match a A more robust version is demaggiggviIa bn a Typical values of K are 10 20 0r50 ofm aka gzumztnc hashmg Combinatorial Point Matching o What ifwe want to match points under arbitrary 8DOF transformations We couldn t do this with images e Fourpoint correspondences are enougn to de ne an 87DOF perspective transformation e Generai idea 0 Hyputhesize fuurpuint correspondences o Sulvefurtransfurmatiun o Evaluate hyputhesis by tne Hausdurff rnetric or tne transfurmed data Geometric Hashing ll Projective Gwen Wu sets uf poms A e as such to m A are a transfurmed subsetuflhe pm nmse added to atthe pumts ms m E vwm En PlckluuvnunrculmeavpumlsmA Fm all pu lblecunespundences E cumpulelhe pvujeclwel quotst Fuveachlvansuvm cumpulel edlslance Hausdom ds13noe Svmmemc m asvmmdno mm Selemlhe mlmmumdlslancevalue Huvv expenswe lsthls7 al vandum 31323334 ulpumls aH lu pumls m m Example 9 l5 nnnrumlnvmlv scaled sheaves and mated lmm mA wm one ema pmm Example ll Assume We chuuse We Wvung pamng muddy pumlslu om pumls as Shawn Wheve doosmo mmdle pmnl Pvn edlm Example Ill A Undevlhlslvansl vmalmn We mlddle puml shuuld mapmmo 12d sle m E Whlch l5 lavlvum anygveen puml m a Example IV However we choose the correct four pomtto four polnt matchlng me Mm pomt m A project onto a data pomt m B Example Jason Denton s PhD l E g quot1 m Notes o The example shown was an affine transformation but it would have Workedlust as Well fora perspective transformation o Some transformations can be dlSmlSSed arpriori 7 Example r points amnme A map in the image in a g lDistruefursumex yinimage e if transfurmatiun Exceeds an m criteria Furaample areralectiunsalluwem if distance image DB l5 computed checking a set of point espondences l5 very fast 0 Combined corner and edge matching 7 Draw eerrespeneeneesrrem Burners if A and a Measure match quality using Edgetu Edge and curnertu eemer distances Notes ll produces perhaps many spurious pol 0 Overall cost for model gt data point matching 0 forperspectivetransformations Meembmatmns times ow Wurk m verify Each 7 O for amne transformations 7 O forsirnilaritytransformations 0 Cost ofdata a data point matching is more why 0 Cost ofmodel a data matching is more is points may be missed why 0 Assume point detector never misses a true point but 39nts 369 Introduction to Computer Vision 0 Definitions 0 Related areas Research and Application Areas Areas listed in Text Book CVPR 1999 Areas Resources Journals amp Conferences Web resources Support Environments 0 What we Will cover this Semester C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 971 Definitions 0 General To endow machines with the ability to see More technical Compute properties of the 3D world from digital imagery Active Control a autonomous processes with the aid of visual input 0 PhysicsMath Resolve mathematically illposed 3D reconstruction problems using general constraints derived from the physics 9 Artificial Intelligence Infer semantically important properties of an environment using prior knowledge C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 92 Related Areas Caveat The following are helpful generalities However realize that they grossly oversimplify a complex topic Image Processing Study of functions from images to images Often called filters Pattern Recognition Partition measurements often vectors into sets Linear classifiers non linear classifiers Photogrammetry Obtain reliable and accurate measurements from noncontact imaging With and Without human assist C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 93 Research Areas Trucco Image Feature Detection Contour representation Feature based Segmentation Range image analysis Shape modeling and representation Shape reconstruction from single image cues Stereo Vision Motion analysis Color Vision Active Vision Invariants Uncalibrated and self calibrating systems 3 D object detection 3 D object location Hi gh perf ormance and real time architectures C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 94 Research Applications Trucco Industrial inspection and quality control Reverse engineering Surveillance and security Face recognition Gesture recognition Road monitoring Autonomous vehicles Hand eye robotics systems Space applications Military applications Medical image analysis Image databases Virtual Reality C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 95 Topic Areas for CVPR 1999 Applications 7 Aerial Image Interpretation Applications 7 Digital and Video Libraries Applications 7 Face Tracking and Recognition Applications 7 Medical Image Analysrs A lications 7 Vision and Document Understanding Applications 7 Vision and Graphics Applications 7 Vision and Robotics Applications 7 Computer Interfaces Color Texture and PhysicsiBased Vision Computational Geometry Low vel Vision Matching and Indexing C5510 r Compuler Graphics Spring 1999 PR 9 29 m gum galuu Model Acquisition Motion Analysis Object Recognition Pattern Analysis Performance Evaluation and Analysis RealiTime Active Vision and Trackin Se gmentation Grouping and Feature Extraction Sensors Shape Representation and Recovery Stereo Vision and Learning J Russ Bevendge Febmry 16 1999 Page 945 Resources Publ1cat1ons Conferences International Conference on Computer Vision ICCV Computer Vision and Patter Recognition CVPR European Conference on Computer Vision ECCV International Conference on Image Processing ICIP International Conference on Pattern Recognition ICPR Journals International Journal of Computer Vision Transactions on Pattern Analysis and Machine Intelligence Computer Vision and Image Understanding Machine Vision and its Applications Image and Vision Computing Journal Pattern Recognition and more C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 97 The Computer Vision Homepage Netscaue he CnmuulerVIxinn HnmEua The Computer Vision Homepage T L m e 9 4 x P D a g9 MAE 39 L ml 80 39 Gsnon Groi lpi Hardware Software Demos Testigg 9 General Info Relnied Links Search a b xsawaarahi o RossEevmdge Febmaryl 1999 Page 94 CS510 r Camputer Graphics Spring 1999 The USC Bibliography u 5 czve imlqes 4 A A 35 Q 17 mezm we we em W Seem sin mm A mp Hm use edustmnrNMesmsenmdhumans my 39wm we Vision Bibliography Rosenfeld 19841994 Table of Cements what is included how to reference it and how n was erea39eei l inuodueuo 2 Rosenfeld Brhirogmmy for 1996 3 Rosenfeld Brhirogmmy for 1995 o a a a H Rosenfeld Brhirogmy for 1934 Counts of authors and uues for BibliogrALhy Onlimpapersmdex contains omymerev metarekmvnwme Au39horsi ihi i i ifigihhilikilimmigiuii msHBiYiEiXiYizi E El gi gihilmk liminigiui liiil u v v x E E 2 E E T Whenaddedi lizi ii ili Si merrmerm Search for we words authors onlimz uue words 4k CS510 7 Computer Graphics Spring 1999 J Ross Beverage February 15 1999 Page 979 Acquiring Digital Images Basic Facts 0 Basic Radiometry 0 Spatial Sampling The continuity assumption Acquisition Noise Perhaps the one correct use of the term noise Camera Parameters Intrinsic Extrinsic C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 9710 Dealing with Noise 0 Different Noise Models Gaussian noise Each measurement slightly in error relative to truth Impulsive noise Small subset of measurements Wildly in error Noise supression Gaussian smoothing Median filtering C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 9711 Recognition Eigenspaces A new idea made possible by Treat images as points in Rn Modern computers are being very powerful and Cost of finding eigenvectors depends upon smaller of I Dimension of embedding space or I Number of samples The approach Project novel image onto first principle components Measure distance to exemplars in this space Used for Face recognition objects on tables etc C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 9712 Image Features Basic Edge Detection Walking through the Canny Algorithm I Conceptual phases I Noise smoothing I Edge enhancements I Edge localization I Criteria for Optimal Edge Detection I Good detection I Good localization I Single response C5510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 9713 1mm P1 4 4 H011 h TIaIleOITnS r ctisWH smW J g 5n 9 14289 I 4cuse4snm jS D I 45255 T 39 9 53510 Compare ampm Spnng 1999 y mam Emle m Fig v u Recognition Interpretation Trees Consider matching a line segments to line segments C A lamina 32 395 quot CS510 Computer Graphics Spring 1999 J Ross Beveridge February 16 1999 Page 9715 Combining Pose amp Matching File Hatch Tir LIZquot a 1 i Luca quot 39 Lucal C3510 Computer Graphics Spring J Ross Beveridge February 16 1999 Page 9 16 Introduction to Features Edges amp Points CS 510 Lecture 23 March 23rd 2009 What is a Feature 0 A feature is anything that is 7 Meaningful 7 Detectaple amp Discrete 0 Features are also intermediate 7 a means no an en 0 Q Are features subimages or structures Examples of Features Edges Corners Chains Line segments Parameterized curves Regions Surface patches Closed Polygons Todays rocus What Is an Edge 0 An edge is a description of a localized image pattern 7 We need to know wnat aspect of tne pattern we are measuring o Facet Mode 0 An edge is a symbolic feature 7 We need to know wnat it denotes o surracc marking or surface discontinuity ur o shaduvvilluminatiun discontinuity 7 These tnings have precise positions The Facet Model Haralick amp Shapiro Vol 1 Chapter 8 u The image can be thought of as a gray level intensity surface 7 piecewise at at facet model 7 piecewise linear sloped facet model 7 piecewise quadratic 7 piecewise cubic 7 Example httgvawmlrametncs cornoncr gm grapnics 2ntrn Processing implicitly or explicitly estimates the free parameters Facet Edge Detection o Facet edge detectors assume a piecewise linear model and calculate the slope of the planarfacet 1st derivative 7 lfwe assurne tnattne noise is zero meari and incre witn tne square ofdlstance tnen convolution witn tne Sobel Edge Operator is optimal 1 2 1 71 0 1 H 0 0 V 72 0 2 71 72 71 71 0 1 MagJH2V2 cane Examples of Facet Edges Suurce Properties of Facet EdgesMasks Magnitude de dyz Orientation tan391 dydx y x responses are signed Edges tend to be thickquot Edge Masks sum ofweights is zero Smuuthmg masks Sum ufvveights is me Symbolic Edge Detection Aithuugh Subei edges are uptimai estimaturs furthe siupe er a pianarfacet m the presence er nuise fur symbuh pdnmses they Ave cuntmuuus need in be threshuided May be inek x need in be incahzed A12 isuiated need in be gvuuped mtu iungev imes ifthey eenespend m seene structure 2 g dismntmmtiesLWE need a mudei er new seene structures map m nnages Canny Edge Detection Step 1 Tu maximizethe hkeimuud uffmdmg stepredges 1SmuuthimagewnhaGaussianMev Sizeisdetevmned hvnmsemadei 2 Cumpute nnege gradients dyenne same SiZE mask Tne biggerthe mask the betterdetectmn is but the WEIrSE incahzatmn is Canny Edge Detection step 2 Nunrmaximai suppressmn enhev neighbm is sndnderu set eddem 12m Dvexei Yutanai mug WAMvgages dvemi eddnwsgzzeen m mm Canny Edge Detection step 3 We smi nave cuntmuuus vaiuesthatvve need m threshuid Aigunthmtakesmmreshuids high mew Any piXEi with edge strength abuvethe high threshuid is an edge Any piXEi abuve the iuwthreshuid and nexttu an ed e is an edge iterativeiy iabei edges they gruvv em nern high paints This is eaued hysteresis Canny Example Canny Example cont J Mg 1 qgf td h 0 Exam is r g i Q g E x I 39 39 t W C J F A ggj mm mm A as quotL 5 M gm Hquot H Xxx I Source image Canny Sigma 2 0 Sigma 3 0 Sigma 1 O lowO40highO9O low04high09 low04high09 Canny Example lll Canny Example IV f w w 3quot ix i a mm e fa cab32 in m Q 6 kg H Mirvase w cg asing H x at Lamb i PH mfg r I is i Sigma 2 0 Sigma 2 0 Sigma 2 0 Sigma 2 0 low04high06 10W04ahlgh099 low02high09 low06high09 Why compute features Second Order Edge Detectors Laplacians Image Contents Matching 0 Alternative approach is to look for zero quot7399 7 quot7399 2 crossings of the approximation to the second derivative 0 NlCe OVeereW httphomepagesinfedacukrbfHPR2Ioghtm Image O Applet http www52ChalmersseresearchimageJavaNeighbEdgeindexhtm lncreasmg Abstraction Features Feature groups Image to Data Matching Image 1 Image Features Feature groups Hierarchical Feature Extraction 0 Most features are extracted by combining a small set of primitive features edges corners regions Grouping which pixels form an edgescornerscurves group Model Fitting what structure best describes the group 0 Simple example The Hough Transform Groups points into lines patented in 1962 Hough Transform Grouping o The idea of the Hough transform is that a change in representation converts a point grouping problem into a peak detection problem 0 Standard line representations y mx b compact but problems with vertical lines x0 yo tx1 y1 your raytracer used this form but it is highly redundant 4 free parameters ax by c O Bresenham s uses this form Still redundant 3 free parameters 0 How else might you represent a line Hough Grouping cont o Represent infinite lines as p Hough Grouping lll 0 Why This representation is Small only two free parameters like ymxb Finite in all parameters 0 lt plt row2co2 0 lt 4 lt 27 Unique only one representation per line 0 General Idea The Hough space p represents every possible line segment Next step use discrete Hough space Let every point vote for any line is might belong to Hough Grouping Directed Edges 0 Every edge has a location and position so it can be part of only one infinitely extended line A I l P o Colinear edges map to one bucket in Hough space I I L V Hough Grouping Edges This reduces hne gruupmg in peak detemun Each edge vmesmv a bucket ime uwmeseguaiesmsuppunwmpanmpaimg edges Pusmun nibucketpmwdesthe ppavametevs Prubiem if true hne parameters are unme buundary at a bucket Suppumng data may be spht Suiutiun smooth the histogram Huugh image befure seiemmg peaks Hough Fitting Anemndmg the peaks m the Huugh Transfurm were are smth putantiai prubiems R esuiutmnhmitedbybucketsize Vuu have emacted mimne hnes nut ime segments Bum ufthese prubiem hnked hst uf edges nut 01 cuuvse tms ismuva expensive s can be xed iF yuu kept a usta uunt Hough Fitting II Sunyuuredges vutateedgepuintsaccuvdmgtu a smmembyumaied xcuuvdmate Luuwur gaps use p wide a maxgap thveshuid mg edges in the suned hst ave mmeman max gap apavt bveakthe ime mtu segments MHEVE ave enuugh edges in a gwen segment a stvaight imetu the pumts Sidebar Fitting Straight Lines to Points in n dimensions umpute the Eigenvaiu Eigenve the iargest Eigenvaqu in 2 dimensions its simmer fur p pmms w 2 35 Evysz e b cusZ t es e mm and take the Eigenvectur assumated With Hough Example Suurce image Huugh Space Hough Example ll Lme data 7 Vote Early and Often Underconstrained Cases 0 In the case ofpoints ratherthan edges 7 oih s ave locations but hotorieha o s 2 7 it is not consistentwith all lines however 0 So points vote for every line they are consistent with 7 more likelyto rihd accidehtai mismatches 7 higher threshold for peailts ih Hough space Under constrained point voting 0 Edge points are consistent with many lines l P 0 They map to many buckets in Hough space 0 Applet u html Finding Circles o This same trick an underconstrained Hough space can be used to nd circles 7 Circles have three parameters Theirentergtlt y Theirradiusr 7 Create a 3D digitized Hough space xyr 0 Every edge with a direction implies a line that the center must lie along 0 The radius is determined by the position ofthe edge ter Circles cont So every edge is consistent with an infinite number of circles These circles lie on a line in 3D parameter space Vote for all of them 7 This is 3D scan line conversion Bresenham y r Circles Two Point Method Consider all pairs of edge points 7 In practice enforce a minimum separation Pairs of edges vote for combinations of radius and image centers Ellipses 52x2 122 5202 o Circles project to ellipses under perspective so can we nd ellipses 0 Limit ourselves to center at the origin major axis along X 7 2 free parameters a amp o 7 Forevery value ora there is a legal value orb 7 Vote roraii aopairs ihthe 2D Hough space 7 Note that the orientation or the edge is not being used o In the Jlly general form ellipses have six parameters Can we apply a Hough space forthis Ray Tracing Intersections Ray to Surface Intersection Calculations are Key Algorithms tied to surface type Sphere Ellipse Cylinder 39 Cone Convex Polygon General Polygon Bicubic Surfaces First pass General Mathematics Second pass Highly Optimized Codes C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4il Representing 21 Ray Hearn Defined by a point and a unit vector P P0 SU The point may be the PRP It may be the pixel If it is the PRP then Pm PM lelx PM CS510 7 Computer Graphics Spring 1999 J Ross Beven39dge January 28 1999 Page Intersecting a Sphere Consider a sphere centered at Pc with radius r 2 2 1 P e POsU PCZ r2O substitute Te a Yielding a quadratic equation sU TsU T r2O CS510 7 Computer Graphics Spring 1999 J Ross Beven39dge January 28 1999 Page Sphere Intersection Continued xcx0 Expand to see What is happening Let T yc yo Zc Z0 ux Ix ux 1x 3 My 1y 0 3 My 1y r20 z tz z tz sax Ix WW r20 W say ty suZ tZ sux tx2suy ty2suZ tz2 r20 C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page44 Sphere Intersection Continued After multiplying out expand and collect s terms th2 uzz uyz 52 2 tyuy thux thuzs txZ r2tZ2ty20 Which may more simply be written as S2 2U TST2 I 2O C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Pageas Sphere Reduces to Quadratic Consider that we now have a simple quadratic equation aszbsc0 Where a1 b2UT cT2 r2 Therefore S bib2 4ac 2a 2UT iX4U T2 4T2 r2 S 2 s UTiW C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page476 Actual Sphere Intersection Points Compute the two s values for the two intersections Sl U T U T2 T2 r2 9 mult1pl1essquares 2 2 2 6 additions 52U39T U39T T r 1 square root Compute the actual positions along the ray 5 mimsl 52 3 multipliessquares p p SU 3 additions l min C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page477 Representing a Ray Foley o Defined by two points P0 and P1 Ptata Po Y xt x0 tx1 x0 W yo ty1 y0 zt z0tzl zo Advantages Easier to carry two points between coordinates 0 More general for intersection computaions CS510 7 Computer Graphics Spring 1999 J Ross Beven39dge January 28 1999 Page Sphere in Parametric Case Consider intersection of Sphere for Parametric Case x0 t dx 131 y01dy Z0IdZ x xc2 y yc2 z zc2 r20 x0tdx xc2y0tdy yc2zOtdz Zc2 r20 Leads to a similar but not identical formulation dx2dz2dy2 t2 2 yo yc dy 2 x0 xc dx 2 z zc dzt x0 xc2 r2 ZO zc2 yo We2 0 C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page49 More on Spheres Closest point based upon t values Example of ray intersection With a sphere E d D dR 6 b D 6122 r2 gt am B d aR 3 multiplies 2 additions 3 multiplies 3 additions 3 multiplies 2 additions 1 root 1 multiply 1 addition 1 root 3 multiplies l additions C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4710 Charlie s Method Simplify by recognizing some similar triangles By Similar Triangles fa 2192c2 and a2b2r2 Solve for t Where tv a and vz f awlr2 b2 gt tv r2 b2 b2262vz Z tv r2czvz c2255 gt tzv W ll 7 multiplies 6 additions 1 square root C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4ill Ellipsoid Intersection Again consider equation for the object an ellipsoid kx xc2ly yc2mz Zc2 r20 Substitute parametric forms for X y and z kx0tdx xc2ly0tdy yc2 mz0tdz zc2 r20 Again we arrive at a quadratic equation a t2 b t C 0 akabc2malz2laly2 921y0 ycdy2kx0 xcdx2mZ0Zcdz Ckc0 cc2mzO zc2lyo yc2 r2 C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4712 Ellipsoids Change the World An alternative and arguably better way is to transform the ray into a world in which the ellipsoid is a shere P r1rP Po 00 xc 0 l PilePil M 0 1 ye 0 0 1 zc 0 0 0 l The equation of the Ellipsoid is now transformed kx xc2ly yc2mz Zc2 r20 a x0tdx2y0tdy2zOtdz2 r20 C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4713 Intersect a Polygon Face For polygonal objects there are two parts Find point of intersection P on infinite plane Is point P inside polygon General equation for a plane in 3D NP p0 gt NPp nxx0tdxnyy0tdynzZ0tdz p0 nxdxnydynzdztnxx0nyy0nzzO p0 nxx0nyy0nZzO p nxdxnydynzdz t NIB p Nils 1 C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4il4 Is the Point Inside the Polygon There are several methods Various implementations of OddEven Parity 5 For convex polygons signed normals 39 Issues Map to true plane of face Orthographic projection to xy X2 or yz C5510 Computer Graphics Spring 1999 J Ross Beveridge January 28 1999 Page4715


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

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Amaris Trozzo George Washington University

"I made $350 in just two days after posting my first study guide."

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."


"Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

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.