CS 664Flexible TemplatesDaniel Huttenlocher2Flexible Template Matching Pictorial structures– Parts connected by springs and appearance models for each part– Used for human bodies, faces– Fischler&Elschlager, 1973 – considerable recent work3Formal Definition of Model Set of parts V={v1, …, vn} Configuration L=(l1, …, ln)– Specifying locations of the parts Appearance parameters A=(a1, …, an)– Model for each part Edge eij, (vi,vj) ∈ E for connected parts– Explicit dependency between part locations li, lj Connection parameters C={cij| eij∈ E}– Spring parameters for each pair of connected parts4Flexible Template Algorithms Difficulty depends on structure of graph– Which parts connected and form of constraint General case exponential time– Consider special case in which parts translate with respect to common origin• E.g., useful for faces•Parts V= {v1, … vn}• Distinguished central part v1• Spring ci1connecting vito v1• Quadratic cost for spring5Efficient Algorithm for Central Part  Location L=(l1, …, ln) specifies where each part positioned in image Best location minL(Σi mi(li) + di(li,l1))– Part cost mi(li) • Measures degree of mismatch of appearance aiwhen part viplaced at each of h locations, li– Deformation cost di(li,l1)• Spring cost ci1of part vimeasured with respect to central part v1• E.g., quadratic or truncated quadratic function• Note deformation cost zero for part v1(wrt self)6Central Part Model Spring cost cij: i=1, ideal location of ljwrt l1– Translation oj=rj-r1– Tj(x)=x+oj Spring cost deformation from this ideal– ⎟⎜lj–Tj(l1)⎟⎜2v1v3v2r1r2r3o2o37Consider Case of 2 Parts minl1,l2(m1(l1) + m2(l2)+⎟⎜l2–T2(l1)⎟⎜2)– Where T2(l1) transforms l1to ideal location with respect to l2(offset) minl1(m1(l1) + minl2(m2(l2)+⎟⎜l2–T2(l1)⎟⎜2))– But minx(f(x) + ⎟⎜x–y⎟⎜2) is a distance transform minl1(m1(l1) + Dm2(T2(l1)) Sequential rather than simultaneous min– Don’t need to consider each pair of positions for the two parts because a distance• Just distance transform the match cost function, m8Overall Computation for 2 Parts  Image and model(translation) Match cost of eachpart m1(l1), m2(l2) Distance transform of m2(l2) minl1(m1(l1) + DTm2(T2(l1))+9Star Graph – Central Reference Part minL(Σi (mi(li) + di(li,l1))) minL(Σi mi(li) + ⎟⎜li–Ti(l1)⎟⎜2)– Quadratic distance between location of part viand ideal location given location of central part minl1(m1(l1) + Σi>1minli(mi(li)+⎟⎜li–Ti(l1)⎟⎜2))– i-th term of sum minimizes only over li minl1(m1(l1) + Σi>1Dmi(Ti(l1)))– Because Df(x) = miny(f(y) + ⎟⎜y-x⎟⎜2)10Star Graph  Simple overall computation– Match cost mi(li) for each part at each location– Distance transform of mi(li) for each part other than reference part• Shifted by ideal relative location Ti(l1) for that part– Sum the match cost for the first part with the distance transforms for the other parts– Find location with minimum value in this sum array (best match) DT allows for flexibility in part locations11Overall Computation for Star Graph  Part costs, O(h) time each, total O(hn) Distance transform non-reference part costs, sum to get MAP location, O(mn) time12More General Flexible Templates Efficient computation using distance transforms for any tree-structured model– Not limited to central reference part – star  Two differences from reference part case– Relate positions of parts to one another using tree-structured recursion• Solve with Viterbi or forward-backward algorithm– Parameterization of distance transform more complex – transformation Tijfor each connected pair of parts13General Form of Problem Best location can be viewed in terms of probability or cost (negative log prob.)– maxLp(L|I,Θ)=argmaxLp(I|L,A)p(L|E,C)– minLΣV mj(lj) + ΣE dij(li,lj)• mj(lj) – how well part vjmatches image at lj• dij(li,lj) – how well locations li,ljagree with model(spring connecting parts viand vj) Difficulty of maximization/minimization depends on form of graph and pairwisecost14Minimizing Over Tree Structures Use dynamic programming to minimizeΣV mj(lj) + ΣE dij(li,lj) Can express as function for pairs Bj(li) – Cost of best location of vjgiven location liof vi Recursive formulas in terms of children Cjof vj– Bj(li) = minlj( mj(lj) + dij(li,lj) + ΣCjBc(lj) )– For leaf node no children, so last term empty – For root node no parent, so second term omitted15Efficient Algorithm for Trees MAP estimation algorithm– Tree structure allows use of Viterbi style dynamic programming• O(nh2) rather than O(hn) for h locations, n parts• Still slow to be useful in practice (h in millions)– Couple with distance transform method for finding best pair-wise locations in linear time• Resulting O(nh) method Similar techniques allow sampling from posterior distribution in O(nh) time– Using forward-backward algorithm16O(nh) Algorithm for MAP Estimate Express Bj(li) in recursive minimization formulas as a DT Df(Tij(li))– Cost function• f(y) = mj(Tji-1(y)) + ∑CjBc(Tji-1(y)) – Tijmaps locations to space where difference between liand ljis a squared distance• Distance zero at ideal relative locations Yields n recursive equations – Each can be computed in O(hD) time• D is number of dimensions to parameter space but is fixed (D generally 2 to 4)17Sampling the Posterior Generate good possible matches as hypotheses– Locations where posterior p(L|I,Θ) large– Validate using another technique• Here use a correlation-like measure (Chamfer) Computation similar to MAP estimation– Recursive equations, one per part– Ability to solve each equation in linear time• Linear time dynamic programming approximation to Gaussian using box filters– Running time under a minute for person model18Sampling Approach Marginal distribution for location lrof (arbitrarily chosen) root partp(lr|I,Θ) = ∑L\lr(∏Vp(I|li,ai) ∏Ep(li,lj|cij)) Can be computed efficiently due to tree structured dependenciesp(lr|I,Θ) ∝ p(I|lr,ar) ∏Chsc(lr) – And fast convolution when p(li,lj|cij) Gaussiansj(li) ∝∑lj(p(I|lj,aj) p(li,lj|cij) ∏Chsc(lj)) Sample location for root from marginal– Sample from root to leaves using p(lj|li,I,Θ)19Samples From Posterior20Sampling from Proposal Distribution