Slide 1Talk PlanTask: Detect Deformable Objects.Deformable TemplatePrior is Markov Random FieldImaging Term:Images and Feature MapsInference by Dynamic ProgrammingResultsLimitationsLong (Leo) Zhu’s PhD ThesisRecursive Compositional Models of Objects (and Images)Applications to Vision Tasks on Benchmarked DatasetsRecursive Compositional ModelsModeling/RepresentationGraph Structure (Tree).Probability DistributionProbabilistic FormulationAND/OR Graph ModelAND/OR Graph for Human BodyAdvantages of Recursive Compositional ModelsInferenceInference.Inference: DP (similar to Constraint Satisfaction)PseudoCodeLearningSupervised LearningStructure-PerceptronStructure Max-MarginUnsupervised Structure Learning10 images for trainingBottom-Up LearningFrom Generic Features to Object StructuresTop-Down LearningResultsMulti-Level Computational ComplexityMore ObjectsSegmentation and ParsingMulti-view Face AlignmentHuman Body ParsingImage ModelImage Parsing: Segmentation-Recognition TemplateImage ParsingComparisonsFeasibility of scaling upSummaryComparisonsRecursive Compositional Models:Modeling, Inference and Learning. Alan YuilleStat. Dept. of UCLALong (Leo) Zhu: PhD ThesisTalk Plan•(I) Discuss Standard Models for Deformable Objects. •Representation/Inference/Learning.•(II) Describe their limitations and motivate:•(III) Recursive Compositional Models.2Task: Detect Deformable Objects.•Example: Detecting Hands by Deformable Templates (Coughlan et al.).•Left: Image of Hand. Right: Deformable Template.3Deformable Template•A Deformable Template can be formulated as a Bayesian model. P(D|W)P(W) – W is configuration of template D is the data (image). Prior P(W) – probable geometry Imaging Model P(D|W). Inference: estimate most probable W*.4Prior is Markov Random Field•q denotes position and orientation of point.•h is an occlusion process.•s is both variables.5Imaging Term:•Extract Features (edges and corners) from the image.6Images and Feature Maps•Examples of edges and corners.7Inference by Dynamic Programming•Perform the MAP estimate: •Compute by Dynamic Programming (DP) by computing partial paths recursively (poly time)Results•MAP estimates of hand configuration.9Limitations •These types of models (c.f. pictorial structures) can be effective but have limitations.•(I) They have only short range spatial interactions (Markov) -- limited modeling.•(II) Dynamic Programming proceeds linearly from thumb to fifth finger – unintuitive.•But if we add dense spatial interactions then: (a) what algorithms can perform MAP?•(b) how to specify, or learn, the dense model? 10Long (Leo) Zhu’s PhD Thesis•More like a research program than a thesis.•9 peer reviewed conference publications.•1 journal publication.•3 journal papers in review.•2 journal papers in preparation.11Recursive Compositional Modelsof Objects (and Images)•Goals: construct models, which enable learning, and perform efficient inference. Unified Approach – one model can perform several vision tasks. General Applicability – applicable to patterns in general (not just images and objects).Inspired by S-C Zhu, D. Mumford, D. Geman.12Applications to Vision Taskson Benchmarked Datasets•Object Categorization, Segmentation and Recognition–Caltech-101 •Deformable Object Detection, Segmentation and Parsing –Weizmann Horse –Multi-view Face Alignment •Articulated Object Parsing–Berkeley Baseball Human Body•Image Parsing: scene labeling–Microsoft Research Cambridge 21-Class 13Recursive Compositional Models The three ingredients: (I) Modeling/Representation – Recursive Compositional Models. (II) Inference – pruned dynamic programming, compositional inference. (III) Learning of Structure and Parameters. Supervised – structure perceptron/max margin. Unsupervised – compositional learning.–.14Modeling/Representation•Recursive Composition of elementary components. Tree Structure.•Triplets 15Graph Structure (Tree).•Probability on graphs16Probability Distribution•Exponential Model. Prior and Data Terms.17Probabilistic Formulation 18•Example of the probabilities.),,,( sPyPxy xyAND/OR Graph Model•A novel AND/OR graph is proposed to model enormous articulated poses.•Learning is performed in a supervised manner.•Applications: Human Body Parsing19AND/OR Graph for Human Body20Advantages of Recursive Compositional Models •(I) Enables modeling of geometric regularities and appearance cues at different scales.•(II) Rich representation – enables different visual tasks to be performed by same model.•(III) Enables effective inference and learning algorithms. •NOTE: Summing out all nodes except the LEAVES gives a dense flat model (computationally intractable).21Inference•Estimate most probable configuration:•Energy can be computed recursively for subtrees:•Enables Dynamic Programming (poly time).2223Inference.•Dynamic Programming (pruned)• (i) keep a list of possible states of child nodes of the tree,•(ii) propose states of the parent nodes. Prune by spatial relationships, overlaps, etc.•Complexity: polynomial in size of image and hierarchy.Inference: DP (similar to Constraint Satisfaction)24PseudoCode•Pseudocode for Dynamic Programming25Learning•Different Types of Learning depending on amount of information available.•Two Cases:•(i) Object boundary labeled. (Supervised).•(II) Object is somewhere in image (Weak Supervision).•(III) One of several objects may be in the image (Unsupervised).26Supervised Learning•Boundary specified on training data.•Two algorithms used for learning:•(i) Structure-Perceptron.•(ii) Structure max-margin.•Both are discriminative learning (not MLE) forcomputational reasons. Both require an inference algorithm (pruned DP).27Structure-Perceptron•Generalization of standard perceptron •(binary outcome ). (simple, but often effective).28Structure Max-Margin•Generalization of Support-Vector Machine29Unsupervised Structure Learning•Procedure: Bottom-Up and Top-Down•Three principles:–Recursive Composition: combine elementary structures (danger combinatorial explosion)–Suspicious Coincidence –Competitive Exclusion •Complexity: linear in the height of a hierarchy (empirically) 3010 images for training31Bottom-Up LearningRepeat from low levels to high levels1. Composition: combine instances from level L2. Clustering: compose concepts at