COMPUTER VISION SYSTEMS
COMPUTER VISION SYSTEMS CAP 6411
University of Central Florida
Popular in Course
Popular in System Engineering
This 93 page Class Notes was uploaded by Khalil Conroy on Thursday October 22, 2015. The Class Notes belongs to CAP 6411 at University of Central Florida taught by Mubarak Shah in Fall. Since its upload, it has received 49 views. For similar materials see /class/227211/cap-6411-university-of-central-florida in System Engineering at University of Central Florida.
Reviews for COMPUTER VISION SYSTEMS
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 10/22/15
Shape Descriptors Desired Properties l Uniqueness l Invariance Size Rotations Translations Noise Moments General Moments 1 If I quotquotV1 B x39d d Discrete Form mm Zprquch r y Uniqueness Theorem I The double moment sequence mm is uniquely determined by BXy and conversely BXy is uniquely determined by mpq Characteristic Function Moment Generating Function Characteristic Function u v J J expiwc ivyBx ydxdy Moment Generating Function Mu v Jexpux vyBx ydxdy Characteristic Function Moment Generating Function Characteristic Function my ivy p q Moment Generating Function M2 mp9 mm H o 9 w F q Muv M V M2 mp 0 a H o F 9 Central Moments y Hmmwv Bxvgt dw davm quot x u quot u Cemmid 7 mm m r Translation Invariant Central Moments Hun mm Eu uu 0 pm U 2 mzu W 11 rm W x pm mm 3mm 2m m mv 2m T2 quot2r 1 4 n 11 mu mu 2mHT 2 11 H mn3 3quotth Hu Moments v1 2 M20 u02 v2 u20 u02 2 4qu v3 u30 3u122 3u12 u03 2 v4 2 M30 uu2 u21 u032 Translation Rotation Scaling Invan39ant Hu Moments V5 an 7 31112 um Jr 12 kuzu Jr 122 73u21uu3zj 31121 uuzxuzlun33u3u Jr 122 uzl uu3z V5 2n WM 1 142 2 i quot21 um 2 4u11u3n Jr 12 X7121 uu3 V7 37121 unzxuzu ulzlul Jr 12Z 73u3u Jr 12ZJ an 3u12u21un33u3u Jr 122 21 uu3 2 Hu Moments Tam IL Mame Inuitnu Infill Illl l in Figs mamla Inwm39m Lay Original Hm39 Size Mmomi Named 239 mm a o 626 am 5253 mm 1 11354 19955 1727 mm 6 2353 21m 22113 1912a 4 247 s 2590 23110 20111 um 4334 537724 45 as m 525 a 2mm 3mm 324m 29 315 48st 53590 45011 mam I In momele Figure 110 Medi39 xis in39a39ns n39m Tim poims on the media axis are the ceq39neis of the maximal ciT aJ neighborhmds Lolally maimed in Lite shape Note ixai Hie veme39rs of We smaller circles SiIOWTE dotted do not constitute iixe medial axis i0 this shape Medial Axis Transform Figure 121 Some examples of media axis transform Medial Axis Transform 1 ILeraiiveiy Compuie f E as follows fwd fUKT l V 1i1 fkI 4 Vpq midi that disizLnchIEIp S l 392 Medial axis is given by all points 4mm such hail FUJI Z ipq Vpr midi ihai 1i514139ncrr1p47 5 1 Figure 420 Hemlith algorithm for con lpuiing media axis transform Medial Axis Transform The barkg39ound a b C Figure 122 Media axis lransfoml a Rerlamgular shape jU j 1quot 3939lll l39 are um shown are all 0 M intermediate step f r The points In Medial axis shown in lwldfaoeh Medial Axis Transform 1 T1 eraiiveb39 mmpme gquot as In ows L k 39 7 max 11iaxg Lq 1 ak l 0 g r1j 7 gm oi39heT39wiSP V014 such LhaL d f SiIL39HftfhhyP S 1 Figure 121 Hera Li ve algorithm for inverse medial axis H39ansform Medial Axis Transform a b C Inverse media axis trans m39n ta MediaI axis gur 11 b hnm39medime s ep Suggested Reading I M K Hu Visual pattern recognition by moment invariants Computer methods in image analysis H Blum A transformation for extracting new descriptors of shape Computer methods in image analysis Chapter 4 Mubarak Shah Fundamentals of Computer Vision Lecture14 Kalman Filter Copyright Mubarak Shah 2003 Main Points Very useful tool It produces an optimal estimate of the state vector based on the noisy measurements observations For the state vector it also provides confidence certainty measure in terms of a covariance matrix It integrates estimate of state over time It is a sequentjaighstateseasymator StateSpace Model State model error With covariance Statetransition equation Qk zk CIDkk 1zk 1wk State Vector Measurement obsenation equation yk Hkzk Vk Observation Nfopyrigm Mubarak Shaf 633 Noise with covariancc easuremen ectorRk Kalman Filter Equations State Prediction 2b k CIk k Did k 1 Covariance Prediction Pbk k k 1Pak 1qTkk 1 Qk Kalman Gain Kk PbkHT kHkPbkHT k Rc 1 Stateupdate ilk it k KkYk H002 16 Covarianceupdate Pa Pb KkHkPb Copyright Mubarak Shah 2003 Two Special Cases kk 1 q Qk Q Hk H Rk R Recursive least squares CIDkk 1I Qk0 Copyright Mubarak Shah 2003 Steady State Comments In some cases state transition equation and the observation equation both may be nonlinear We need to linearize these equation using Taylor series Copyright Mubarak Shah 2003 Extended Kalman Filter zk fzk 1wk Yk hzk Vk N A 8fzk 1 A fZk 1fZak 1 alkl Zk 1 Zak 1 Taylor series A 6hz k hltzltkgtgt hltzbltkgtgt aZ k Copyright Mubarak Shah 2003 ZOO211164 Extended Kalman Filter zk fzk 1 wk mm 1 Zkfiak1 6204 Zk1iak1Wk zk m kk 1zk 1uk wk uk fiak 1 CDkk 1iak 1 mam m 3106 1 Copyright Mubarak Shah 2003 CDkk 1 Extended Kalman Filter Ykhzkvk 6hzk A azk 1k Zbk 1Vk 37k z Hkzk vk Wk NO hib k H0021 k ahZk 5106 Copyright Mubarak Shah 2003 WC hibk Hk MultiFrame Feature Tracking Application of Kalman Filter Copyright Mubarak Shah 2003 Assume feature points have been detected in each frame We want to track features in multiple frames Kalman filter can estimate the position and uncertainty of feature in the next frame Where to look for a feature how large a region should be searched Copyright Mubarak Shah 2003 pk xbykr Location vk 1ka Velocity Z X10 ykaukavkT State Vector Copyright Mubarak Shah 2003 System Model pk pk71 Vk71 4 ng noise Vk Vk l 77k 1 Zk qDIHZIH WH 1 o 0 1 9t kel 1 o Wk71 0 1 77171 ubarak Shah 2003 1 0 DIM 0 0 EOOHO Copyright Measurement Model 1000pk yquot 0100vk W P Vk Measureme t matrix Copyright Mubarak Shah 2003 Kalman Filter Equations State Prediction ibk k k 1iak 1 Covariance Prediction mic c13kk71Pak71CIDTkk71 Qk Kaiman Gain Kk PbkHTkHkPbkHT k Ric l Stateupdate 2506 ibk KkYk Hkibk Covarianceupdate Pa Pb k7KkHkPb Cupynght Mubarak snan mus Cupynght Mubarak snan mus Kalman Filter Relation to Least Squares fl Z yi 0 Taylor series flani0may lty yigtltz iigtwi az Y H1Zwl A A 6 A 6 Y Zxr1ayxszr1aHzL Bz Bz if A W yy ay Copyright Mubarak Shah 2003 Kalman Filter Relation to Least Squares Estimate state such that the following is minimized first term initial estimate weighted by corresponding covariance second term other measurements weighted by corresponding covariances A A k C z0 ZTPO 1Z0 Z 2 Y1 HiZTW 1Yx HiZ il minimize A k A k z P04 ZHKVWHPOZO ZHfm lm 11 11 Batch Mode Copyright Mubarak Shah 2003 Kalman Filter Relation to Least Squares k k zk P04 ZHfW Hir1iIrlzo ZHfW2m i1 i1 A H A k4 ZH P1 Pglzo ZHKWSYJ 1 1 i1 Recursive Mode Copyright Mubarak Shah 2003 Kalman Filter Relation to Least Squares Zk Zk71 Kk Yk HkZH Kk PkAHTk Wk HkPkelHkT71 Pk 1 KkaPc71 T 6f qk k 1 1 Y f Zkrlayk71EZkrl Z 0 H Covariance matrix for measurement k 6Z Vector y T Wk 1A l Copyright Mubarak Shah 2003 5y 5y Kalman Filter Least Squares State Prediction 2b k k k 1iak 1 Mk Mk 1 Covariance Prediction Pb k k k 1Pak 1 Tkak 1 Qk P1 k Pak 1 Kalman KUC Pb HT kHkPb HT 0 Rk71 Gain Kk P17 HT kHkPl7 HT 0 Wk71 Copyright Mubarak Shah 2003 Kalman Filter Least Squares Stateupdate 211k 2500 Hkibk i ki k1KkYkHki 161 Covarianceupdate Pak Pb k KkHkPb k P k P k 1 KkHkP k 1 Copyright Mubarak Shah 2003 Computing Motion Trajectories Copyright Mubarak Shah 2003 Algorithm For Computing Motion Trajectories Compute tokens using Moravec s interest operator intensity constraint Remove tokens which are not interesting with respect to motion optical flow constraint Optical flow of a token should differ from the mean optical flow around a small neighborhood Copyright Mubarak Shah 2003 Algorithm For Computing Motion Trajectories Link optical flows of a token in different frames to obtain motion trajectories Use optical flow at a token to predict its location in the next frame Search in a small neighborhood around the predicted location in the next frame for a token Smooth motion trajectories using Kalman filter Copyright Mubarak Shah 2003 Kalman Filter Ballistic Model 2 xZ 5axl vxlx0 Zax3ay3vxjvy W 50 vyf yo y xryr fZy x0 lt50sz w x0yl my vyz y0 Copyright Mubarak Shah 2003 Kalman Filter Ballistic Model Zk Zk 1 KkYk HkZk 1 Kk Pk 1HTk Wk HTPk 1HTk 1 Pk 1 K kH kPk 1 Yk7fTZk71y ZF Zk71 af HkaZ 0f OfT W k Ak 3 3 Copyright Mubarak Shah 2003 15 m h i Lecture1 1 Structure from Motion Copyright Mubarak Shah 2003 Problem Given optical flow or point correspondences compute 3D motion translation and rotation and shape depth Copyright Mubarak Shah 2003 Tomasi and Kanade Orthographic Projection Copyright Mubarak shah 2003 Assumptions The camera model is orthographic The positions of p points in f frames fgt3 which are not all coplanar have been tracked The entire sequence has been acquired before starting batch mode Camera calibration not needed if we accept 3D points up to a scale factor Copyright Mubarak shah 2003 Tomasi amp Kanade u jy j f1Fp1P Copyright Mubarak Shah 2003 SpXPYPZP gag11mm T ufP lfsP Zf VfP jSP Zf kf l f upjthmz amkshahl l Orthographic projection quotI f Cupyngql Mubamk Shah mu 1 P lsp tf Zlsq tf q iJT SPZSq T Origin of world is at the l S centroid of object points f Cowgght Mubarak shah 2003 N T g2 H i N T va fSP N Copyright Mubarak shah 2003 N T N u l s U fP f P N 7 T S W fP J f P V if lT N f W T s1 sP RS 11 3XP jf Rank ofS is 3 because points in 3D space are not 2FX3 Copyright Mubarak shah 2003 c0p1anar Rank Theorem Without noise the registered measurement matrix W is at most of rank three T 11 T N 1 W Qsl SPRS Jr 3XP jT 2FX3 Copyright Mubarak shah 2003 Translation quDZu af u 17 a T 1f f u j zfsp ufp lfSp af ZiSp tf af is projection of camera translation along Xaxis Copyright Mubara Sha 00 Translation f2 lfSp If pr 2 stp bf T W RS tep 2FX3 3XF 2FX1 1Xp ta1afb1bfT e 4 I3 1l211khah2003 Translation Projected camera translation can be computed 1 P T lftf af 32 p1 1 P T ftf be 32 1111 Copyright Mubarak shah 2003 Noisy Measurements Without noise the matrix must be at most of rank 3 When nois corrupts the images however M will not be rank 3 Rank theorem car be extended to the case of noisy measurements Copyright Mubarak shah 2003 Approximate Rank W 0202 ZFXP PXP PXP Copyright Mubarak shah 2003 Singular Value Decomposition SVD For some linear systems Axb Gaussian Elimination or LU decomposition does not work because matrix A is singular or very close to singular SVD will not only diagnose for you but it will solve it Copyright Mubarak shah 2003 Singular Value Decomposition SVD Theorem Any m by n matrix A for which m 2 ncan be written as A0 mxn mxn X X 0301 0 02 1 2 is diagonal 01 02 are orthogonal Copyright Mubarak shah 2003 Singular Value Decomposition SVD lfA is square then 01202 are all square 71 T a A OZO 0 05 1 2 2391 diagi mxn mxn nxn nxn W J A 01202 1 A 1 Ozcl39zag O1 Cjzpyn39ght Mubarak shah 2003 Singular Value Decomposition SVD The condition number of a matrix is the ratio ofthe largest of the W to the smallest of W A matrix is singular if the condition number is infinite it is illconditioned if the condition number is too large Copyright Mubarak shah 2003 Singular Value Decomposition SVD Ax b lfA is singular some subspace of x maps to zero the dimension of the null space is called nullity Subspace of b which can be reached by A is called range of the dimension of range is called rank of A Copyright Mubarak shah 2003 Range and Null Space Range of A Dimension of Null space of A range is rank of A Dimension of Null space is Nullblt bank 51121112003 Singular Value Decomposition SVD lfA is nonsingular its rank is lfA is singular its rank ltn Ranknullityn Copyright Mubarak shah 2003 Singular Value Decomposition SVD A 01202 SVD constructs orthonormal basses of null space and range Columns of 01 with nonzero w J spans range Columns of 02 with zero w spans null space Copyright Mubarak shah 2003 Solution of Linear System How to solve Axb when A is singular If b is in the range of A then system has many solutions Replace by zero if 00 x Ozidiagltinofb CopyrightWybamk shah 2003 Solution of Linear System If b is not in the range of A above eq still gives the solution which is the best possible solution it minimizes rEle bl Copyright Mubarak shah 2003 Approximate Rank 3 P3 W 01202 01 01 01 2F 3 P3 2 03 2 0 2 P3 0 3 02 0 P3 Copyright Mubarak shah 2003 P 01202 01392390 01392 0g Approximate Rank W 01202 0120 02 0 W 01392390 The best rank 3 approximation to the ideal registered measurement matrix Copyright Mubarak shah 2003 Rank Theorem for noisy measurement The best possible shape and rotation estimate is obtained by considering only 3 greatest singular values of W together With the corresponding left right eigenvectors Copyright Mubarak shah 2003 Approximate Rank R 239 Approximate Rotation matrix A 1 S 0 Approximate Shape matrix A A A LL This decomposition is not unique A A 71 A I I I W S Mgaiask 311 2336 1nvertab1e matr1x Copyn39 Approximate Rank R How to determine Q 1 A T T 1 S Q S If QQ If R andS are linear transformation of f I 1 approximate Rotation and shape matrices Rows of rotation matrix are unit vectors Copyright Mubarak shah 2003 and orthogonal How to determine Q Newton s Method frq iTQQTiT 1 0 Mqug 220 391TQQT1T 1 0 f3 l1TQQTJAI1T 0 Aq AqrAq9 3 M 1 f3Hq ffTQQTf 1 0 391 aqj fam 1 0 Sis error 2 q 2 QQT 0 Copyright Mubarak shah 2003 Algorithm Compute SVD of W 01202 de ne 1 0139239 3 21 0 Compute Q ComputeR S 2 13 Copyright Mubarak shah 2003 Hotel Sequence Selected Features Cupyngm Mubarak Shah mu Comparison cavnd39 um mm House Sequence Reconstructed Walls cva mammxm tomasiTI92Figgespdf cva mammxm Web Page httpvisionstanfordeducgi binsvlpublicationpublication1992cgi Copyright Mubarak Shah 2003 22 Recognizing Facial Expressions Lecture1 3 Copyright Mubarak Shah 2003 Homework Due November 11 Lecture 9 slide 17 slide 22 Lecture 12 page 21 and 22 three problems Copyright Mubarak Shah 2003 Program 11 Due November 16 Implement Mean shift Algorithm for tracking Assume that the object location is given in the rst frame of the seq Demonstrate your program on known test seqs Demonstrate your program on unknown test seqs in the lab Write a short report method problems results observations Copyright Mubarak Shah 2003 Facial expressions re ect the emotional stage of a person 39 Recognizing facial expression from video sequences is a challenging problem Applications Perceptual user interface Video compression MPEG4 Synthesis of facial expressions Copy ghtMubmkShnhZOM Facial Expressions Joy The eyebrows are relaxed The mouth is open and mouth corners pulled back toward ears Sadness The inner eyebrows are bent upward The eyes are slightly closed The mouth is relaxed Anger The inner eyebrows are pulled downward and together The eyes are wide open The lips are pressed against each other or opened to expose teeth Copyright Mubarak Shah 2003 Facial Expressions Fear The eyebrows are raised and pulled together The inner eyebrows are bent upward The eyes are tense and alert Disgust The eyebrows and eyelids are relaxed The upper lip is raised and curled often asymmetrically Surprise The eyebrows are raised The upper eyelids are wide open the lower relaxed The jaw is open Copyright Mubarak Shah 2003 FACIAL EXPRESSIONS RAISE EYE BROWS SMILE Copyright Mubamk Shah 2003 FACIAL EXPRESSIONS DISGUST Copyright M WQ R Black and Yacoob Algorithm Given the location of the face eyes brows and mouth estimate the rigid motion of the face using pseudo perspective motion model Use the face motion to register images through warping Estimate relative motion of face features eyes mouth brows The estimated feature motions are used to predict locations of features in the next frame and the process is repeated The estimated motion is used to classify the facial expressions Copyright Mubarak Shah 2003 Rigid Face I TldllblUlll a IUII Face Planar V Nonrigid 7 a i f Facial Feafu es 3 i39 Eyes Affine Mouth Brows Affine Curvature Mmibamk Sham 2W3 Af ne ux y a1xa2yb1 vxy a3x a4y b2 01 2 uxy x y 1 O O 0 b1 vxy 0 O 0 x y l av3 a4 b2 Copyright Mubarak Shah 2003 Af ne ux y alx azy bl vx y a3x a4y b2 Expansion or contraction zvergence ux V a1 a4 Rotation aroundZ curl uy vx a2 as s hin 8 deformatzon ux vy a1 a4 Pseudo Perspective ux y a1 azx a3 y a4x2 asxy 2 Vxay 39 a6 a7xasy a4xy as a4yaw rotation around yaxis a5pitchz rotation around xaxis Z 3 quotXJ l x y 12 xy 0 0 0 vxy000xyy21xy 1 59 95 0 Copyright Mubarak Shah 2003 0 Pseudo Perspective ux y a1 azx a3y a4x2 asxy vxy a6 a7xa8ya4xy asy2 a4yaw a5pitch Af ne with Curvature ux y azlxazyb1 vx y a3xal4yb2 ch at a 0 0 1 JE as uxyxy100 vxy 000xy copyright Mubarak Shah 2003 Rules for Classifying Expressions Anger B inward lowering of brows and mouth contraction E outward raising of brows and mouth expansion Disgust B mouth horizontal expansion and lowering of brows E mouth contraction and raising of brows Happiness B upward curving of mouth and expansion or horizontal deformation E downward curving of mouth and contraction or horizontal deformation 3 1 MI 2003 Rules for Classifying Expressions Surprise B raising brows and vertical expansion of mouth E lowering brows and vertical contraction of mouth Sadness B downward curving of mouth and upwardinward motion in the inner parts of brows E upward curving of mouth and downwardoutward motion in inner parts of brows 0 Fear B expansion of mouth and raisinginwards inner parts of brows M M2093 E contraction of mouili an owenng inner parts of brows Smile Expression I J Upwaurltgla wlmaml my H M1 LQILE 7 Pm EETTlhleS g m vc 39 g1 cumvaimfca Iquot l EL E 391 l Manual mimsinl i DE 539 I a I IncaIian I I I quot EtmLe39velI rrr r Emmi 5 39 39IIILe39uePi f 39 39 39 39 39 39 39 quot42 I I I I I Emmm a and Wazra V wim j gimme Inuuimg Icagmquot inim 1V in amp a g E j D f 5 Iii Ending r OMInt I I ll l39Namnhan I z x I I 133 mud I I VII A v l I 6 m YI W11 A47 quotquotf b 9 no lV f PH Igv mag 1qu IIIam Hams m wwmm by awning pp 39 lIuI Of 069 mm h Minibamk Sbk39a uh 2W3 Smila M NH 39I39I39 U i v 1 m J 3639 1w 17 Figure 3 Smile rxpLri moer racial e xprmsiml Lraclcing Smile Mouth Parameters Copyright Mubank Shah 2003 Anger if if in M V Iquot ii iii if I 145 151 55 Figure If Anger experiment facial cxprmsion hacking FiraLurua every 5 frames Mmlbam k Sbk39a uibl ZWE Angar Mmian Parameters duutll u m i g l r l a A I A I I uL Diuenjence 39unlaiu39re Ugfomnh on Bruws Eyes i 1 i 1 in L u gt4 1 L 39 239 Z I I 39 IE I L h n M L h l I I Ham39mnta I lertiml Divemencs l g x by IIw In gt i 39u I 1 J a 1 T l 39unmtu m l 39ll Defamation Figure 1 Anger muLiml paratnclmrs he mlid lim indicaum Llur righL 13quot or brow while Lhc dashed line indicalc IJH 391 1311 or bruw Surprise 2H 19 Vlu 11th E l 3 u 39J knnaz m a nn Ul39vsmsncs sformatmn Bruws h 1 1 a l l 3 nh I39Erhmu39 ur Hahn39s Eye u L 39 Defm39mntlon Blinking r 25 639 9 2m a H 5 g a 215 273 250 25 Figure 14 Blinking txpur39irnan racial FcaLuru tracking H aLu za every 011139 frames Mmlbam k Swag 22m Blinking Motion Parameters for Eyes Copyright Mubarak Shah 2003 Ratate Page matiLQn parameters j I I L l I luv D m fL AV 5 n n n a u u n n 1 n a u u i anm aam 31mm Diusmsncs 0 m V In Lr L EA I I hr Deformation Mm mmk Sbk wibl 201013 RQta m M0ti n Paramet rs hluuth Brows H I J I i 1 l 1 la v 4 i h hhL h i r m Thunm ntmn unmhm Verizon q I J I I g a x 7 14 4 I J L Dimmmre Defoer hon V 39uruu tum 9 m Mubarak 8mm 2mm Midlevel predicates for Mouth Copyright Mubarak Shah 2003 Midl vel predicates far Hem fable 4 l he midIrwsl pmdiralms derived 1qu dfl ij l39l l i fl and muLiun panamahm usLimalm a applivd 0 head muLI39KJn an 0 1 39 5 H and tin Inmward 11 l H and anracliml Il l Head sIcrLical deformation c 410415 HosId munLcrrlnCk wise mLaLiml 395 2 110 39 1 Head around Lh ock 1 1101141115 H and bark ward C39wmmiwhdi Mm brm Shim mm 5quot i Parameter values used for classifying expressions Copyright Mubarak Shah 2003 Results Expression Rate Surprise 91 Happiness 95 Anger 90 Disgust 93 Fear 83 Sadness 100 Copyright Mubarak Shah 2003 Beginning of Anger Expression copyright Mubarak Shah 2003 39 I I I 1mm 141 nnrrl N l I re 3912 er 04 quotI I l 1 3939 39 H3939 I39m rm 1 39H IV 391 H r rm rrIlt139 L I I 39 39 H r L u39 39 3939vl u l3939H39 JIL n E Results Expression Rate Surprise 86 Happiness 95 Anger 80 Disgust 50 Fear 100 Sadness 60 httpwwwcfarumdedu p39IRsCVLRepom1995TR340lBlackpsgz Copyright Mubarak 8112112003