### Create a StudySoup account

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

Already have a StudySoup account? Login here

# 685 Class Note for CSE 598F at PSU

### View Full Document

## 29

## 0

## Popular in Course

## Popular in Department

This 77 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at Pennsylvania State University taught by a professor in Fall. Since its upload, it has received 29 views.

## Similar to Course at Penn State

## Popular in Subject

## Reviews for 685 Class Note for CSE 598F at PSU

### 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: 02/06/15

Robert Collins CSE598G Intro to Template Matching and the LucasKanade Method Robert Collins CSE598G AppearanceBased Tracking current frame r prevrous location iim r p g gt nr 9 7 M vii 7 vv F likelihood over object location current location in e ModeSeeking eg meanshift LucasKanade particle filtering Robert Collins CSE598G Basic Template Matching Assumptions a snapshot of object from rst frame can be used to describe appearance Object will look nearly identical new image Movement is nearly pure 2D translation The last two are very restrictive We will relax them later on Robert Collins CSE598G Template Matching Is a search problem Given an intensity patch element in the left image search for the corresponding patch in the right image We will typically need geometric constraints to reduce the size of the search space But for now we focus on the matching function Ruben Camus csEsny Correlationbased Algorithms Elements to be matched are image patches of fixed size Task What is the corresponding patch in a second image iwnaam Ruben Cullins csEsny Correlationbased Algorithms Task What is the corresponding patch in a second image 3 39 I L E 1 1 1 Need an appearance similarity function 2 Need a search strategy to nd location with highest similarity Simplest but least ef cient approach is exhaustive search Robert Collins CSE598G Comparing Windows 2 E i 1 m l 1 Some possnble measures WEB Z fij gz39j 7416 SSD Z fltz39j gzj2 WEB Mos r Cfgz Z fz39jgz39j Popular ER Robert Collins CSE598G Correlation Cfg ER If we are doing exhaustive search over all image patches in the second image this becomes cross ccrrelaticn of a template With an image Robert Collins CSE598G Stereo pair of the El Capitan formation from the NASA mars rover mission Image 1 Image 2 These slides use a stereo pair but the basic concepts are the same for matching templates across time Robert Collins CSE598G Template image patch Robert Collins CSE598G Example Crosscorrelation score im lterimage2tmpl Score around correct match Highest scog V 39 quot I it Correct match Robert Collins CSE598G Example Crosscorrelation Note that score image looks a lot like a blurry version of image 2 This clues us in to the problem with straight correlation with an image template Robert Collins csme Problem with Correlation of Raw Image Templates Consider correlation of template with an image of constant grey value a b e V V V d e f 69 V V V g h i V V V Result Vabcdefghi Robert Collins csme Problem with Correlation of Raw Image Templates Now consider correlation with a constant image that is twice as bright a b c 2V 2V 2V d e f 69 2V 2V 2V g h i 2V 2V 2V Result 2Vabcdefghi gt vabcdefghi Larger score regardless of what the template is Robert Collins Em Solution Subtract off the mean value of the template In this way the correlation score is higher only when darker parts of the template overlap darker parts of the image and brighter parts of the template overlap brighter parts of the image Robert Collins CSE598G Correlation zeromean template A u Better But highest score is still not the correct match Note highest score IS best Within local neighborhood of correct match gggrgsgo ins SSD or block matching Sum of Squared Differences 2 NJ gz39j2 ER 1 The most popular matching score 2 We will use it for deriving the LucasKanade method 3 TruccoampVerri 486 textbook claims it works better than crosscorrelation Camps PSU Robert Collins CSE598G Relation between SSD and Correlation SSD X f g2 MGR Z f2 Z 92 2 iajER 7571655 ER Correlation Robert Collins CSE598G S Best match highest score in image coincides with correct match in this case Ruben Cullins Em Handling Intensity Changes the camera taking the second image might have different intensity response characteristics than the camera taking the rst image 39111umination in the scene could change The camera might have autogain control set so that it s response changes as it moves through the scene Ruben Cullins E59 Handling Intensity Changes Handling Intensi Changes One approach is to estimate the change in intensity and compensate for it eg Background Estimation under Rapid Gain Change in Thennal Imagery Yalcin Collins and Hebert 2nol IEEE Workshop on Object Tracking and classification in andBeyond the Visible Spectrum OTCBVS39OS June 2005 The second approach is to use a normalized matching function that is invariant to intensity changes This is the one we Will be discussing now Robert Collins CSE598G Intensity Normalization When a scene is imaged by differenT sensors or39 under39 differenT illuminaTion inTensiTies boTh The 55D and The Cfg can be large for39 windows r39epr39esenTing The same area in The scene A soluTion is To NORMALIZE The pixels in The windows befor39e comparing Them by subTr39acTing The mean of The paTch inTensiTies and dividing by The sTddev ff v E U fig if E Robert Collins CSE598G Normalized Cross Correlation Highest score also coincides with correct match Also looks like less chances of getting a wrong match Robert Collins Em Normalized Cross Correlation Important point about NCC Score values range from 1 perfect match to 1 completely anticorrelated Intuition treating the normalized patches as vectors we see they are unit vectors Therefore correlation becomes dot product of unit vectors and thus must range between 1 and 1 Ruben Cullins csEsny Voluntary Exercise Let f be an image patch and let g be the same patch except with grey values modified by a multiplicative intensity gain factor and an additive intensity offset g gain f offset Consider the norm alized patches 6 a Robert Collins CSE598G Some Practical Issues 0 Object shape might not be well described by a scanlineoriented bounding rectangle We end up including lots of background pixels in our foreground template Robert Collins CSE598G Some Practical Issues 0 One solution use a Gaussian windowing function to weight pixels on the object more highly and weight background pixels zero W 7 a q39 7 4quot r 7 7 gt a If s v Works best for compact objects like vehicles Robert Collins CSES98G Some Practical Issues Problem Don t want to search Whole image Solution bound search radius for object based on how far it can move between frames Need some estimate of object motion and camera motion if camera is moving Works best over short time periods Robert Collins CSE598G Correlation Sample Code Properties Correlation of normalized template Use Gaussian windowing function computed from user supplied box in rst frame Search window for object centered at previous object location best for small motion I ll put code on the course web site Robert Collins Em Normalized Correlation Fixed Template template Failure mode distraction by background clutter Robert Collins CSES98G Normalized Correlation Fixed Template template Failure mode Unmodeled Appearance Change Robert Collins CSE598G Naive Approach to Handle Change One approach to handle changing appearance over time is adaptive template update One you nd location of object in a new frame just extract a new template centered at that location What is the potential problem Robert Collins CSE598G Template If your estimate of template location is slightly off you are now looking for a matching position that is similarly off center Over time this offset error builds up until the template starts to slide off the object The problem of drift is a major issue with methods that adapt to changing object appearance Robert Collins CSES98G Normalized Correlation Adaptive Template template Here our results are no better than before Robert Collins CSE598G Normalized Correlation Adaptive Template template Here the result is even worse than before Robert Collins CSE598G Tracking Via Gradient Descent Robert Collins CSE598G Motivation Want a more ef cient method than explicit search over some large window If we have a good estimate of object position already we can ef ciently re ne it using gradient descent Assumption Our estimate of position must be very close to where the object actually is however we can relax this using multiscale techniques image pyramids Rob en Collins E59 Math Example 1D Gradient Consider function fX 100 05 XAZ F e m mew Insevt Van s oesmp wmgw He v DEBS h QWE DE a m2 1m mm 99 BE 97 95 95 94 93 Robert Collins Em Math Example 1D Gradient Consider function fX 100 05 X Z Gradient is dfXdX 2 05 X X Geometric interpretation gradient at X0 is slope of tangent line to curve at point X0 tangent line Ay slope Ay AX dfXdx X 0 Rob en Collins E59 Math Example 1D Gradient fX 100 05 XAZ dfxdx x F e m mew Insevt Van s oesmp wmgw He v DEBS h QWE DIE a m2 1m grad slope 2 mm 99 1 BE 97 95 95 94 93 Rob en Collins E59 Math Example 1D Gradient fX 100 05 XAZ dfxdx x F e m mew Insevt Van s oesmp wmgw He v DEBS m aa39sm n a39 m2 1m mm 99 BE 97 95 95 94 93 Rob er Collins CSE598G fX 100 05 XAZ MIIHH I 1 on this side of peak are positive Gradients Math Example 1D Gradient dfXCHX XD H av iwwv w Jn fleet D My Gradients 1 i on this side of peak are negative gm 396 Note Sign of gradient at point tells you What direction to go to travel uphill Robert Collins E59 Math Example 2D Gradient fXy 100 05 XAZ 05 yquot2 dfXydX X dfXydy y Gradient dfXydX dfXydy X y 3 ii 1quot3 Gradient is vector of partial deriys wrt X and y aXes Rnhert Cnllins Em Math Example 2D Gradient fXy 100 05 XAZ 05 yAZ Gradient dfXydx dfXydy X y Plotted as a vector field the gradient vector at each pixel points uphill The gradient indicates the direction of steepest ascent The gradient is 0 at the peak also at any at spots and local minima but there are none ofthose for this function Rnh an Cullins E598 Math Example 2D Gradient fXy 100 05 XAZ 05 yAZ Gradient dfXydx dfXydy X y Let ggxgy be the gradient vector at pointpixel x0y0 Vector g poinm uphill direction ofsteepest ascent Vector g points downhill direction ofsteepest descent Vector gy gx is perpendicular and denotes direction of constant elevation ie normal to contour line passing through point X0y0 Rnh 211 Cullins m Math Example 2D Gradient fXy 100 05 XAZ 05 yAZ Gradient dfXydx dfXydy X y And so on for all points Robert Collins E59 What is Relevance of This consider the SSD error function Shifted a quotV Window v function This tells how match score changes if you shift the template by uv Robert Collins Em What is Relevance of This In locality of correct match the function EuV looks a little bit like too 95 i an actually it looks like an upside down version of this as since we are looking for a A minimum Therefore we should be able to use gradient descent to find the best offset uV 0f the template in the new frame Robert Collins CSE598G Review Numerical Derivatives See also TruccoampVerri Appendix A2 Taylor Series expansion V 1af 1 W fix h fix iizrquotcx1 5Wquot ix ah x 0m Manipulate r r l q l l fix 1 fix hf irJ 3 11quot iii1 0U f hii NI DUI 139 Finite forward difference Ruben Cullins csEsny Numerical Derivatives See also TampV Appendix A2 Taylor Series expansion few1 rm 7 hf xhzf x 731713f x 0W Manipulate fxgtfltxeh hf ltxh2f x0013 fix wah h f 0l1 Finite backward difference Ruben Cullins csEsny Numerical Derivatives See also TampV Appendix A2 Taylor Series expansion mm x hquotltxgt 92 th 0M f397 h 7 fx 7 1 39x 121 Wm 7 31713 Wm 0014 fx17fxih 2hf x 32713f x 0014 f h 7 f 7 1 2h fx 0hz Finite central difference Robert Collins CSE598G Numerical Derivatives See also TampV Appendix A2 Finite forward difference h fij ii Finite backward difference f if f X h h f x 00 fix OH Finite central difference More fix h 3 ff h frm m fij accurate 5 39l Robert Collins CSE598G Harris Detector Mathematics Change of intensity for the Shift 24 u quotshifted Y39 Windnw Window function W 1 in window 0 outside Gaussian Ruben Cullins csEsny Taylor Series for 2D Functions fxuy v fXy u xy vj xy First p artial derivatives 1 5 Mlmy MW vim M Second partial derivatives 1 391 ulmm iv ML Livmoi vr mom 39 Third partial derivatives Higher order terms First order approx fb my V z fX y fx U MOW Ruben Cullins csEsny LucasKanade Derivation Euv 2 IX uyv 7 Txy2 E xy Lllrx39 17402 7 Txyz First order approx 2 mm v1 ltxygt Dltxygt12 Take partial derivs and set to zero SE a 2 Wm v1vltxvgt DltwgtJ my 0 2 umw v1 w DltwgtJ1rltwgt 0 Form matrix equation If I ll u AD solvevia 2 JV 7 V 2 YD leastrsquares Robert Collins CSE598G LucasKanade Tracking Robert Collins CSE598G Lucas Kanade Tracking Traditional LucasKanade is typically run on small cornerlike features e g 5X5 to compute optic flow Observation There s no reason we can t use the same approach on a larger window around the object being tracked Robert Collins CSE59SG Lucas Kanade Tracking Assumption of constant ow pure translation for all pixels in a larger Window is unreasonable However we can easily generalize LucasKanade approach to other 2D parametric motion models like af ne or projective Robert Collins CSE598G Warping Review translation 7 44 Euclidean aitme x FIGURE 1 Bzhi 39 set of 2D plzmzu39 tnmsfoi nmtiom picture from RSzeliski Robert Collins CSE598G Geometric Image Mappings Geometric image xy transformation gt transformed image X y X fx y parameters y gx y parameters Robert Collins CSE598G Linear Transformations Can be written as matrices image xy Hltlt Geometric transformation gt transformed image X y X Mparams y 1 Ruben Cullins csEsny X xl y 1quot equations Translation transform xv matrix form Ruben Cullins csEsny X xl y 1quot equations Translation transform xv matrix form Robert Collins CSE598G Scale y 1 transform 3 J x 5 l U x 1 51 U H r 1 5 U 53 quot 1 0 U 1 1 equations matrix form Robert Collins Em Rotation y transform 9 A 3quot H sinB J Aquot x cos WSJiIiH 1 L95 l V quot smH 038 0 y SHE 18 wigmat 1 U U 1 equations matrix form Ruben Cullins csmc Euclidean Rigid y transform 1 0 o 1 X V 7 x XC059 iysine h X n e bme r X 1 9 056th y sme 6059 y y 71mm M I 0 0 l 1 equations matrix form Ruben Cullins 05w Partitioned Matrices 1quot case isine 1r X J sin 6 cos 9 V L 1 l 31 11 31 matrixform l 0 l 1 pr R1 1 equation form Ruben Cullins C555 Similarity scaled Euclidean p stt equations matrix form Ruben Cullins csEsny e transform 7 p 7 Ab p Ii411 1701 1 equations matrix form Robert Collins CSE598G Projective transform J Ap b pquot b p I CT39J 1 717 it 1 1 equations matrix form Robert Collins CSE598G Summary of 2D Transformations rotation translation scale aspect ratio perspective warp Robert Collins CSE598G Summary of 2D Transformations Euclidean translation scale aspect ratio perspective warp Robert Collins CSE598G Summary of 2D Transformations Similarity translation aspect ratio 3 1 perspective warp Robert Collins CSE598G Af ne Summary of 2D Transformations translation aspec i ratio perspective warp Robert Collins CSE598G Summary of 2D Transformations Projective translation aspect ratio perspective warp Rob en Collins E59 Summary of 2D Transformations N aino Matrix DOF Preserves Icon translation I I t LN 2 orientatitm rigid Euclidean R t M 3 lengths 1 similarity SR I t 2A3 4 angle 4 af ne A kw 3 parallelism E pnjjoctivo H law 8 straight lines table from RSzeliski Robert Collins CSE598G to be continued

### 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

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

#### "Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

#### "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!"

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

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.