### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Class Note for COSC 6373 with Professor Shah at UH

### View Full Document

## 28

## 0

## Popular in Course

## Popular in Department

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

## Reviews for Class Note for COSC 6373 with Professor Shah at UH

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

Image alignment Imagealiimenti 9tian Panorama stitching Recognition of object instances em balenges Image al Occlusion clutter Image alignment A Two broad approaches I Direct pixelbased alignment I Search for alignment where most pixels agree I Featurebased alignment I Search for alignment where extracted features agree Can be verified using pixelbased alignment Alignment as fitting Lasf iectUre fitting arrimwo39cTel to featuresin one image M Find model M that minimizes 2 residualx M Alignment as fitting 0 Last ieEture fitting amodie39l to featuresin one image M Find model M that minimizes 2 residualx M Alignment fitting a model to a transformation between pairs of features matches in two images xi Find transformation T T 139 that minimizes 0 39 gt 939 o 077 39 ZresidualTxix 39 i Featurebased aliinment ouline Kine ment outl Featurebased align Extract features Featurbased ajgnmnt outlin Extract features 0 Compute putative matches Featu rb ase aj39nment outline Extract features Compute putative matches Loop I Hypothesize transformation Tsma group of putative matches that are related by T Featurbase ajinment outline Extract features Compute putative matches Loop I Hypothesize transformation Tsma group of putative matches that are related by T I Verify transformation search for other matches consistent with T Featurbased ajgnment outlin Extract features 0 Compute putative matches Loop I Hypothesize transformation Tsma group of putative matches that are related by T I Verify transformation search for other matches consistent with T 2D transformation models Similarity translation scale rotation o Affine Projective homography Let s start with affine transformations o smd fti procedure linear least squares o Approximates viewpoint changes for roughly planar objects and roughly orthographic cameras Can be used to initialize fitting for more complex models Fitting an affine anSf mamm 0 Assume we knowitheicbrFespohdencesvrhOw do we get the transformation xiy xiayi t e 0 0 of o 0 m1 0 x m1 m2 xi t1 xi yi 0 0 1 0 m3 x I I yi m3 m4 yi t2 0 0 xi yi 0 1 m4 yi t1 t2 Fitting an affine transformatiom xyl0010m3x l Ooxiyi01m4 yi Linear system with six unknowns Each match gives us two linearly independent equations need at least three to solve for the transformation parameters What if we d0l39 t know the correspondences What if we donquotj know the correspondences feature feature descriptor descriptor Need to compare feature descriptors of local patches surrounding interest points Feature descriptors Assuming the patches areialready normalized ie the local effect of the geometric transformation is factored out how do we compute their similarity 0 Want invariance to intensity changes noise perceptually insignificant changes of the pixel pattern I c u 39 5 a Feature descriptors Simplestdescri ptor vc tor o raw intensity values 0 How to compare two such vectors I Sum of squared differences SSD SSDuv 2111 vi2 I Not invariant to intensity change I Normalized correlation puav 2104 7 7Vi 17 l2 lm l I Invariant to affine intensity change Feature descriptors Disadvantage df patChesas de Eriptors I Small shifts can affect matchin scor a lot Solution h anquot 1 39 x p x I I lt 0 2P Feature descriptorsggSIFzT Descriptor computation I Divide patch into 4x4 subpatches I Compute histogram of gradient orientations 8 reference angles inside each subpatch I Resulting descriptor 4X4X8 128 dimensions q David G Lowe quotDistinctive image features from scaleinvariant kevpoints IJCV6O 2 pp 91110 2004 Feature descriptors SIFT Descriptorfcomputation if I Divide patch into 4X4 subpatches I Compute histogram of gradient orientations 8 reference angles inside each subpatch I Resulting descriptor 4x4x8 128 dimensions Advantage over raw vectors of pixel values I Gradients less sensitive to illumination change I Subdivide and disorderquot strategy achieves robustness to small shifts but still preserves some spatial information David G Lowe quotDistinctive image features from scaleinvariant kevpoints IJCV6O 2 pp 91110 2004 Feature matching Generating pUtatve matches for each patch in one image find a shont list of patches in the other image that could match it based solely on appearance Feature matching Generatingputativemat ves for each patch in one image find a short list of patches in the other image that could match it based solely on appearance I Exhaustive search For each feature in one image compute the distance to all features in the other image and find the closest ones threshold or fixed number of top matches I Fast approximate nearest neighbor search I Hierarchical spatial data structures kdtrees vocabulary trees I Hashing Feature space outlier rejectm o How can we tell which putative matches are more reliable o Heuristic compare distance of nearest neighbor to that of second nearest neighbor I Ratio will be high for features that are not distinctive I Threshold of 08 provides good separation 05 07 r 06 FDF lor correct matches 4 PDF lor incorrect matches 05 FDF 04 2239 A x XL W quota 0 01 02 03 04 05 06 07 03 09 1 Ratio at distances closestnext closest 01 0 David G Lowe quotDistinctive image features from scaleinvariant keypointsquot IJCV60 2 pp 91110 2004 Dealing with outliers Theset of butative matches still 39contains a very high percentage of outliers How do we fit a geometric transformation to a small subset of all possible matches 0 Possible strategies I RANSAC I Incremental alignment I Hough transform I Hashing Strategy mRANSAG puswrvr RANSAC looplt i 39 Randomly select a seed group of matches Compute transformation from seed group Find inliers to this transformation If the number of inliers is sufficiently large re compute leastsquares estimate of transformation on all of the inliers Keep the transformation with the largest number of inliers RANSAC example Translation Putative matches RANSAC example Translation Select one match count inliers RANSAC example Translation Select one match count inliers RANSAC example Translation Find average translation vector Problem with RAQSAC f o In many practicalsituations thepercentage of outliers incorrect putative matches is often very high 90 or above 0 Alternative strategy restrict search space by using strong locality constraints on seed groups and iniers I Incremental alignment Strategyz Ivn rel11ental alignment r o Takeadvantage o1 trong locality constraints only pick closeby matches to start with and gradually add more matches in the same neighborhood 8 Lazebnik C Schmid and J Ponce Semilocal affine parts for obiect reooqnition BMVC 2004 Strategyz Incremental alignment Take advantage of strong locality constraints only pick close by matches to start with and gradually add more matces in thgsamnhborxod x 7 X Strategyz Incremental alignment Take advantageiof strong I ocaility conStr aintsfonly pick close by matches to start with and gradually add more matces in the ne bo hood Strategyz Incremental alignment Take advantage of strong locality constraints only pick close by matches to start with and gradually add rnore matces in thgsame nhborod 1er quot T X Strategyz Incremental alignment Take advantage of strong locality constraints only pick close by matches to start with and gradually Incremental alignment Details image 1 image 2 I Generating seed groups I Identify triples of neighboring features i j k in first image I Find all triples i j k in the second image such that i resp j k is a putative match of i resp j k and j k are neighbors of i Incremental alignment Details o I Beginning with each seed triple repeat I Estimate the aligning transformation between corresponding features in current group of matches I Grow the group by adding other consistent matches in the neighborhood I Until the transformation is no longer consistent or no more matches can be found Incremental alignment Details I imageZ I Beginning with each seed triple repeat I Estimate the aligning transformation between corresponding features in current group of matches I Grow the group by adding other consistent matches in the neighborhood I Until the transformation is no longer consistent or no more matches can be found image 1 Incremental alignment Details image 1 I Beginning with each seed triple repeat I Estimate the aligning transformation between A Q image 2 CD corresponding features in current group of matches I Grow the group by adding other consistent matches in the neighborhood I Until the transformation is no longer consistent or no more matches can be found Incremental alignment Details image 1 I Beginning with each seed triple repeat I Estimate the aligning transformation between A Q image 2 CD corresponding features in current group of matches I Grow the group by adding other consistent matches in the neighborhood I Until the transformation is no longer consistent or no more matches can be found Strategy 3 Hoth transform Suppose our features are scale and rotationinvariant I Then a single feature match provides an alignment hypothesis translation scale orientation David G Lowe quotDistinctive imaqe features from scaleinvariant keypointsquot IJCV60 2 pp 91110 2004 Strategy 3 Hough transform Suppose our features arei39scale and rotationinvariant I Then a single feature match provides an alignment hypothesis translation scale orientation I Of course a hypothesis obtained from a single match is unreliable I Solution let each match vote for its hypothesis in a Hough space with very coarse bins model David G Lowe quotDistinctive image features from scaleinvariant keypointsquot IJCV60 2 pp 91110 2004 Recall Generalized Hough transform l visual codeword with displacement vectors test image B Leibe A Leonardis and B Schiele Combined Obiect Cateqorization and Seqmentation with an implicit Shape Model ECCV Workshop on Statistical Learning in Computer Vision 2004 Houghxtransform details D Lowe ss39ystemi 0 Training phase For each model feature reCord 2D location scale and orientation of model relative to normalized feature frame 0 Test phase Let each match between a test and a model feature vote in a 4D Hough space I Use broad bin sizes of 30 degrees for orientation a factor of 2 for scale and 025 times image size for location I Vote for two closest bins in each dimension 0 Find all bins with at least three votes and perform geometric verification I Estimate least squares af ne transformation I Use stricter thresholds on transformation residual I Search for additional features that agree with the alignment David G Lowe quotDistinctive image features from scaleinvariant kevpoints IJCV6O 2 pp 91110 2004 Strategy 4 Hashing 7 V V Make each invariant image feature into a lowdimensional key that indexes into a table of hypotheses hash table Strategy 4 Hashing i Eke each invariant image feature into a lowdimensional key that indexes into a table of hypotheses Given a new test image compute the hash keys for all features found in that image access the table and look for consistent hypotheses hash table StrateggyA Hays 0 Make each invariant image feature into a lowdimensional key that indexes into a table of hypotheses 0 Given a new test image compute the hash keys for all features found in that image access the table and look for consistent hypotheses o This can even work when we don t have any feature descriptors we can take ntuples of neighboring features and compute invariant hash codes from their geometric configurations Bev afinetrsformtis Whajcmis raisfari vieitiveen 39to viws of a planar surface o 7 0 Fl 7 Fl 7 O H 3V 9 O quot 3 Q j Ea Beyond affine transformations o Homography planeprcajective transformation transformation taking a quad to another arbitrary quad In I Fitting a hongQVaPhyv Recall homogenenou coordinates a a ay gt 9 9 gt mwayw 1 w Converting to homogenenous Converting from homogenenous image coordinates image coordinates Fitting a homograP39W Recall homogenenou coordinates a a ay gt 9 9 gt mwayw 1 w Converting to homogenenous Converting from homogenenous image coordinates image coordinates Equation for homography 3quot hm 1112 113 x A y h21 h22 h23 y 1 731 I732 I733 1 Fitting a yhommograAphy Equation for homographyi 95 hm h2 1113 xi 1 y 1721 I122 I123 yi i i 1 1131 1132 h 1 hi 9 entries 8 degrees of freedom scale is arbitrary y hgxi hgxi ngHXi0 xngxi thxi xghgxl x hixi y hfxi 0T xz T y XiT h1 XiT 0T x X1 h2 0 3 equations only 2 linearly y XIT x Xquot Or 113 Independent Direct linear transform Ah 0 5395quot N H O b T n KT 0 xx o H has 8 degrees of freedom 9 parameters but scale is arbitrary 0 One match gives us two linearly independent equadons Four matches needed for a minimal solution null space of 8X9 matrix 0 More than four homogeneous least squares tchingu Application Panorama st Recognizig anoramas Given contents of a camera memory card automatically figure out which pictures go together and stitch the ther into anoramas M Brown and D Lowe Recognizing Panoramas ICCV 2003 httpwwwosubooambrownpanoramapanoramahtml 1 Estimate homography RANSAC te homogl aphy RANSAC 1 Estima cpnnected sets 9f images 2 Find connected sets 9f images P 3 Stitch and blend the panoramas Issues in alignmentbasedapplications Choosing the geometric alignment model I Tradeoff between correctness and robustness also efficiency 0 Choosing the descriptor I Rich imagery natural images highdimensional patch based descriptors eg SIFF I Impoverished imagery eg star fields need to create invariant geometric descriptors from ktuples of point based features 0 Strategy for finding putative matches I Small number of images onetime computation eg panorama stitching brute force search I Large database of model images frequent queries indexing or hashing I Heuristics for featurespace pruning of putative matches Issues in alignmentbasedapplications Choosing the geometric alignment model 0 Choosing the descriptor Strategy for finding putative matches Hypothesis generation strategy I Relatively large inlier ratio RANSAC I Small inlier ratio locality constraints Hough transform Hypothesis verification strategy I Size of consensus set residual tolerance depend on inlier ratio and expected accuracy of the model I Possible refinement of geometric model I Dense verification 6056 6373 Computer Vision Image Alignment Acknowledgement Notes by Profs R Szeliski S Seitz S Lazebnik and S Shah

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

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

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

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