Markov Nets Dhruv Batra, 10-708 Recitation 10/30/2008Contents • MRFs – Semantics / Comparisons with BNs – Applications to vision – HW4 implementationSemantics • Bayes NetsSemantics • Markov NetsSemantics • Decomposition – Bayes Nets – Markov NetsSemantics • Factorization • What happens in BNs?Semantics • Active Trails in MNs • What happens in BNs?Semantics • Independence Assumptions Markov Nets Bayes Nets Global Ind Assumption, d-sep Local Ind Assumptions Markov Blanket10-708 – ©Carlos Guestrin 2006-2008 10 Representation Theorem for Markov Networks If H is an I-map for P and P is a positive distribution Then Then H is an I-map for P If joint probability distribution P: joint probability distribution P:Semantics • Factorization • Energy functions • Equivalent representationSemantics • Log Linear ModelsSemantics • Energies in pairwise MRFs • What is encoded on nodes and edges?Semantics • Priors on edges – Ising Prior / Potts Model – Metric MRFsMetric MRFs • Energies in pairwise MRFsApplications in Vision • Image Labelling tasks – Denoising – Stereo – Segmentation, Object Recognition – Geometry EstimationMRF nodes as pixels Winkler, 1995, p. 32MRF nodes as patches image patches Φ(xi, yi) Ψ(xi, xj) image scene scene patchesNetwork joint probability scene image Scene-scene compatibility function neighboring scene nodes local observations Image-scene compatibility function ∏ ∏ Φ Ψ = i i i j i j i y x x x Z y x P ) , ( ) , ( 1 ) , ( ,Application • Motion EstimationStereoGeometry EstimationGeometry EstimationHW4 • Interactive Image SegmentationHW4 • Pairwise MRF X1X2X3X4X5X6X7X8X9Y1Y2Y3Y4Y5Y6Y7Y8Y9HW4HW4 • Step 1: GMMs • Step 2: Adjacency matrix / MRF Structure • Step 3: MRF parameters • Step 4: Loopy BP • Step 5: Segmentation MasksSlide Credits • Bill Freeman, Fredo Durand, Lecture at MIT – http://groups.csail.mit.edu/graphics/classes/CompPhoto06/html/lecturenotes/2006March21MRF.ppt • Charles A. Bouman – https://engineering.purdue.edu/~bouman/ece641/mrf_tutorial/view.pdf • Fast Approximate Energy Minimization via Graph Cuts, Yuri Boykov, Olga Veksler and Ramin Zabih. IEEE PAMI 23(11), November 2001. • Make3D: Learning 3-D Scene Structure from a Single Still Image, Ashutosh Saxena, Min Sun, Andrew Y. Ng, To appear in IEEE PAMI
View Full Document