{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,5]],"date-time":"2026-04-05T05:38:24Z","timestamp":1775367504714,"version":"3.50.1"},"reference-count":177,"publisher":"Emerald","issue":"3-4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,5,23]]},"abstract":"<jats:p>Powerful statistical models that can be learned efficiently from large amounts of data are currently revolutionizing computer vision. These models possess a rich internal structure reflecting task-specific relations and constraints. This monograph introduces the reader to the most popular classes of structured models in computer vision. Our focus is discrete undirected graphical models which we cover in detail together with a description of algorithms for both probabilistic inference and maximum a posteriori inference. We discuss separately recently successful techniques for prediction in general structured models. In the second part of this monograph we describe methods for parameter learning where we distinguish the classic maximum likelihood based methods from the more recent prediction-based parameter learning methods. We highlight developments to enhance current models and discuss kernelized models and latent variable models. To make the monograph more practical and to provide links to further study we provide examples of successful application of many methods in the computer vision literature.<\/jats:p>","DOI":"10.1561\/0600000033","type":"journal-article","created":{"date-parts":[[2011,5,24]],"date-time":"2011-05-24T02:30:52Z","timestamp":1306204252000},"page":"185-365","source":"Crossref","is-referenced-by-count":137,"title":["Structured Learning and Prediction in Computer Vision"],"prefix":"10.1561","volume":"6","author":[{"given":"Sebastian","family":"Nowozin","sequence":"first","affiliation":[{"name":"Microsoft Research Cambridge ,","place":["United Kingdom"]}]},{"given":"Christoph H.","family":"Lampert","sequence":"additional","affiliation":[{"name":"IST Austria, Institute of Science and Technology Austria ,","place":["Austria"]}]}],"member":"140","published-online":{"date-parts":[[2011,5,23]]},"reference":[{"key":"2026032614563874200_ref001","first-page":"91","volume-title":"Local Search in Combinatorial Optimization","author":"Aarts","year":"1997"},{"key":"2026032614563874200_ref002","first-page":"75","volume-title":"Workshop on Discrete Optimization","author":"Ahuja","year":"2002"},{"key":"2026032614563874200_ref003","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2008.4587402","article-title":"Reduce, reuse & recycle: Efficiently solving multi-label MRFs","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Alahari","year":"2008"},{"key":"2026032614563874200_ref004","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2010.5540123","article-title":"Efficient piecewise learning for conditional random fields","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Alahari","year":"2010"},{"key":"2026032614563874200_ref005","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2009.5206754","article-title":"Pictorial structures revisited: People detection and articulated pose estimation","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Andriluka","year":"2009"},{"issue":"B","key":"2026032614563874200_ref006","first-page":"213","article-title":"Two \u201cwell-known\u201d properties of subgradient optimization","volume":"120","author":"Wolsey","year":"2009","journal-title":"Mathematical Programming"},{"key":"2026032614563874200_ref007","article-title":"Learning with blocks: Composite likelihood and contrastive divergence","volume-title":"Conference on Uncertainty in Artificial Intelligence (AISTATS)","author":"Asuncion","year":"2010"},{"issue":"3","key":"2026032614563874200_ref008","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/s101070050002","article-title":"The volume algorithm: Producing primal solutions with a subgradient method","volume":"87","author":"Barahona","year":"2000","journal-title":"Mathematical Programming"},{"key":"2026032614563874200_ref009","volume-title":"Bayesian Reasoning and Machine Learning","author":"Barber","year":"2011"},{"issue":"8","key":"2026032614563874200_ref010","doi-asserted-by":"crossref","first-page":"1239","DOI":"10.1109\/TPAMI.2005.161","article-title":"Generalizing swendsen-wang to sampling arbitrary posterior probabilities","volume":"27","author":"Barbu","year":"2005","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref011","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2010.5539951","article-title":"Beyond trees: MRF inference via outer-planar decomposition","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Batra","year":"2010"},{"key":"2026032614563874200_ref012","article-title":"Tighter relaxations for MAP-MRF inference: A local primal-dual gap based separation algorithm","volume-title":"Conference on Uncertainty in Artificial Intelligence (AISTATS)","author":"Batra","year":"2011"},{"key":"2026032614563874200_ref013","volume-title":"Nonlinear Programming","author":"Bertsekas","year":"1995","edition":"2nd"},{"key":"2026032614563874200_ref014","volume-title":"Network Optimization","author":"Bertsekas","year":"1998"},{"key":"2026032614563874200_ref015","volume-title":"Introduction to Linear Optimization","author":"Bertsimas","year":"1997"},{"key":"2026032614563874200_ref016","first-page":"179","article-title":"Statistical analysis of non-lattice data","volume-title":"The Statistician","author":"Besag","year":"1975"},{"issue":"3","key":"2026032614563874200_ref017","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1111\/j.2517-6161.1986.tb01412.x","article-title":"On the statistical analysis of dirty pictures","volume":"B-48","author":"Besag","year":"1986","journal-title":"Journal of the Royal Statistical Society"},{"issue":"4","key":"2026032614563874200_ref018","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1109\/34.677269","article-title":"A pixel dissimilarity measure that is insensitive to image sampling","volume":"20","author":"Birchfield","year":"1998","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref019","volume-title":"Pattern recognition and machine learning","author":"Bishop","year":"2006"},{"key":"2026032614563874200_ref020","first-page":"428","article-title":"Interactive image segmentation using an adaptive GMMRF model","volume-title":"European Conference on Computer Vision (ECCV)","author":"Blake","year":"2004"},{"key":"2026032614563874200_ref021","volume-title":"European Conference on Computer Vision (ECCV)","author":"Blaschko","year":"2008"},{"key":"2026032614563874200_ref022","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2009.5206699","article-title":"Structured output-associative regression","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Bo","year":"2009"},{"key":"2026032614563874200_ref023","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-05078-1","volume-title":"Numerical Optimization","author":"Bonnans","year":"2003"},{"key":"2026032614563874200_ref024","first-page":"1737","article-title":"SGD-QN: Careful Quasi-Newton stochastic gradient descent","volume":"10","author":"Bordes","year":"2009","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"2026032614563874200_ref025","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Bottou","year":"2007"},{"issue":"9","key":"2026032614563874200_ref026","doi-asserted-by":"crossref","first-page":"1124","DOI":"10.1109\/TPAMI.2004.60","article-title":"An Experimental Comparison of Min-Cut\/Max-Flow Algorithms for Energy Minimization in Vision","volume":"26","author":"Boykov","year":"2004","journal-title":"PAMI"},{"key":"2026032614563874200_ref027","first-page":"648","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Boykov","year":"1998"},{"issue":"11","key":"2026032614563874200_ref028","doi-asserted-by":"crossref","first-page":"1222","DOI":"10.1109\/34.969114","article-title":"Fast approximate energy minimization via graph cuts","volume":"23","author":"Boykov","year":"2001","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref029","first-page":"105","article-title":"Interactive graph cuts for optimal boundary and region segmentation of objects in N-D images","volume-title":"International Conference on Computer Vision (ICCV)","author":"Boykov","year":"2001"},{"key":"2026032614563874200_ref030","first-page":"3241","article-title":"Constrained parametric min-cuts for automatic object segmentation","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Carreira","year":"2010"},{"key":"2026032614563874200_ref031","first-page":"2089","article-title":"Enforcing topological constraints in random field image segmentation","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Chen","year":"2011"},{"key":"2026032614563874200_ref032","volume-title":"Branch and Bound Algorithms\u2014Principles and Examples","author":"Clausen","year":"1999"},{"key":"2026032614563874200_ref033","first-page":"1","article-title":"Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms","volume-title":"Conference on Empirical methods in Natural Language Processing","author":"Collins","year":"2002"},{"key":"2026032614563874200_ref034","volume-title":"Decomposition Techniques in Mathematical Programming","author":"Conejo","year":"2006"},{"key":"2026032614563874200_ref035","first-page":"951","article-title":"Ultraconservative online algorithms for multiclass problems","volume":"3","author":"Crammer","year":"2003","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"2026032614563874200_ref036","article-title":"Residual belief propagation: Informed scheduling for asynchronous message passing","volume-title":"Uncertainty in Artificial Intelligence (UAI)","author":"Elidan","year":"2006"},{"key":"2026032614563874200_ref037","first-page":"66","article-title":"Efficient matching of pictorial structures","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Felzenszwalb","year":"2000"},{"issue":"1","key":"2026032614563874200_ref038","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s11263-006-7899-4","article-title":"Efficient belief propagation for early vision","volume":"70","author":"Felzenszwalb","year":"2006","journal-title":"International Journal of Computer Vision (IJCV)"},{"key":"2026032614563874200_ref039","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1145\/1390156.1390195","article-title":"Training structural SVMs when exact inference is intractable","volume-title":"International Conference on Machine Learing (ICML)","author":"Finley","year":"2008"},{"issue":"1","key":"2026032614563874200_ref040","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1109\/T-C.1973.223602","article-title":"The representation and matching of pictorial structures","volume":"22","author":"Fischler","year":"1973","journal-title":"IEEE Trans. Computer"},{"key":"2026032614563874200_ref041","volume-title":"Practical Methods of Optimization","author":"Fletcher","year":"1987"},{"key":"2026032614563874200_ref042","volume-title":"Optimization for Machine Learning","author":"Franc","year":"2011"},{"issue":"1","key":"2026032614563874200_ref043","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/s10479-005-3447-9","article-title":"About lagrangian methods in integer optimization","volume":"139","author":"Frangioni","year":"2005","journal-title":"Annals of Operations Research"},{"key":"2026032614563874200_ref044","first-page":"939","article-title":"Energy minimization via graph cuts: Settling what is possible","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Freedman","year":"2005"},{"issue":"1","key":"2026032614563874200_ref045","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1023\/A:1026501619075","article-title":"Learning low-level vision","volume":"40","author":"Freeman","year":"2000","journal-title":"International Journal of Computer Vision (IJCV)"},{"key":"2026032614563874200_ref046","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Frey","year":"1997"},{"key":"2026032614563874200_ref047","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2009.5459175","article-title":"Class segmentation and object localization with superpixel neighborhoods","volume-title":"International Conference on Computer Vision (ICCV)","author":"Fulkerson","year":"2009"},{"issue":"3","key":"2026032614563874200_ref048","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF00115697","article-title":"A common framework for image segmentation","volume":"6","author":"Geiger","year":"1991","journal-title":"International Journal of Computer Vision (IJCV)"},{"issue":"6","key":"2026032614563874200_ref049","doi-asserted-by":"crossref","first-page":"721","DOI":"10.1109\/TPAMI.1984.4767596","article-title":"Stochastic relaxation, Gibbs distributions and the Bayesian restoration of images","volume":"6","author":"Geman","year":"1984","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref050","doi-asserted-by":"crossref","first-page":"82","DOI":"10.1007\/BFb0120690","article-title":"Lagrangian relaxation for integer programming","volume":"2","author":"Geoffrion","year":"1974","journal-title":"Mathematical Programming Study"},{"issue":"4","key":"2026032614563874200_ref051","first-page":"473","article-title":"Practical Markov chain Monte Carlo","volume":"7","author":"Geyer","year":"1992","journal-title":"Statistical Science"},{"key":"2026032614563874200_ref052","first-page":"305","article-title":"Exponential priors for maximum entropy models","volume-title":"Human Language Technology Conference of the North American Chapter of the Association for Computational Linguistics (HLT-NAACL)","author":"Goodman","year":"2004"},{"issue":"2","key":"2026032614563874200_ref053","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1007\/BF02579036","article-title":"Lagrangean relaxation","volume":"11","author":"Guignard","year":"2003","journal-title":"TOP"},{"key":"2026032614563874200_ref054","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF02592954","article-title":"Lagrangean decomposition: A model yielding stronger Lagrangean bounds","volume":"39","author":"Guignard","year":"1987","journal-title":"Mathematical Programming"},{"key":"2026032614563874200_ref055","volume-title":"Finite Markov Chains and Algorithmic Applications","author":"H\u00e4ggstr\u00f6m","year":"2000"},{"issue":"2","key":"2026032614563874200_ref056","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","article-title":"A formal basis for the heuristic determination of minimum cost paths","volume":"4","author":"Hart","year":"1968","journal-title":"IEEE Transactions on Systems Science and Cybernetics"},{"key":"2026032614563874200_ref057","first-page":"97","article-title":"Monte Carlo sampling methods using Markov chains and their applications","volume-title":"Biometrika","author":"Hastings","year":"1970"},{"key":"2026032614563874200_ref058","article-title":"Multiscale conditional random fields for image labeling","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"He","year":"2004"},{"key":"2026032614563874200_ref059","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1613\/jair.1933","article-title":"Convexity arguments for efficient minimization of the Bethe and Kikuchi free energies","volume":"26","author":"Heskes","year":"2006","journal-title":"Journal of Artificial Intelligence Research (JAIR)"},{"issue":"6","key":"2026032614563874200_ref060","doi-asserted-by":"crossref","first-page":"409","DOI":"10.6028\/jres.049.044","article-title":"Methods of conjugate gradients for solving linear systems","volume":"49","author":"Hestenes","year":"1952","journal-title":"Journal of Research of the National Bureau of Standards"},{"issue":"8","key":"2026032614563874200_ref061","doi-asserted-by":"crossref","first-page":"1771","DOI":"10.1162\/089976602760128018","article-title":"Training products of experts by minimizing contrastive divergence","volume":"14","author":"Hinton","year":"2002","journal-title":"Neural Computation"},{"issue":"10","key":"2026032614563874200_ref062","doi-asserted-by":"crossref","first-page":"1333","DOI":"10.1109\/TPAMI.2003.1233908","article-title":"Exact optimization for Markov random fields with convex priors","volume":"25","author":"Ishikawa","year":"2003","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"1","key":"2026032614563874200_ref063","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/s10994-009-5108-8","article-title":"Cutting-plane training of structural SVMs","volume":"77","author":"Joachims","year":"2009","journal-title":"Machine Learning"},{"key":"2026032614563874200_ref064","article-title":"Lagrangian relaxation for MAP estimation in graphical models","volume-title":"Allerton Conference on Control, Communication and Computing","author":"Johnson","year":"2007"},{"key":"2026032614563874200_ref065","first-page":"503","volume-title":"Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21\u201324, 2010, Haifa, Israel","author":"Jojic","year":"2010"},{"issue":"2","key":"2026032614563874200_ref066","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1023\/A:1007665907178","article-title":"An introduction to variational methods for graphical models","volume":"37","author":"Jordan","year":"1999","journal-title":"Machine Learning"},{"key":"2026032614563874200_ref067","first-page":"703","article-title":"The cutting-plane method for solving convex programs","volume-title":"Journal of the Society for Industrial and Applied Mathematics","author":"Kelley Jr","year":"1960"},{"key":"2026032614563874200_ref068","first-page":"96","article-title":"Bayesian estimation of smooth parameter maps for dynamic contrast-enhanced MR images with block-ICM","volume-title":"CVPR Workshop on Mathematical Methods in Biomedical Image Analysis, Computer Vision and Pattern Recognition","author":"Kelm","year":"2006"},{"issue":"6","key":"2026032614563874200_ref069","doi-asserted-by":"crossref","first-page":"988","DOI":"10.1103\/PhysRev.81.988","article-title":"A Theory of Cooperative Phenomena","volume":"81","author":"Kikuchi","year":"1951","journal-title":"Physical Review"},{"key":"2026032614563874200_ref070","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2011.5995645","article-title":"Variable grouping for energy minimization","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Kim","year":"2011"},{"key":"2026032614563874200_ref071","doi-asserted-by":"crossref","first-page":"671","DOI":"10.1126\/science.220.4598.671","article-title":"Optimization by simulated annealing","volume":"220","author":"Kirkpatrick","year":"1983","journal-title":"Science"},{"issue":"1","key":"2026032614563874200_ref072","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/0262-8856(84)90040-4","article-title":"Contextual classification of multispectral pixel data","volume":"2","author":"Kittler","year":"1984","journal-title":"Image Vision Computing"},{"key":"2026032614563874200_ref073","article-title":"MAP inference in discrete models","volume-title":"Tutorial at ICCV 2009","author":"Kohli","year":"2009"},{"key":"2026032614563874200_ref074","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2007.383204","article-title":"P3 & beyond: Solving energies with higher order cliques","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Kohli","year":"2007"},{"key":"2026032614563874200_ref075","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2008.4587417","article-title":"Robust higher order potentials for enforcing label consistency","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Kohli","year":"2008"},{"issue":"3","key":"2026032614563874200_ref076","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1007\/s11263-008-0202-0","article-title":"Robust higher order potentials for enforcing label consistency","volume":"82","author":"Kohli","year":"2009","journal-title":"International Journal of Computer Vision (IJCV)"},{"key":"2026032614563874200_ref077","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller","year":"2009"},{"issue":"10","key":"2026032614563874200_ref078","doi-asserted-by":"crossref","first-page":"1568","DOI":"10.1109\/TPAMI.2006.200","article-title":"Convergent tree-reweighted message passing for energy minimization","volume":"28","author":"Kolmogorov","year":"2006","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"issue":"7","key":"2026032614563874200_ref079","doi-asserted-by":"crossref","first-page":"1274","DOI":"10.1109\/TPAMI.2007.1031","article-title":"Minimizing nonsubmodular functions with graph cuts-A review","volume":"29","author":"Kolmogorov","year":"2007","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"issue":"2","key":"2026032614563874200_ref080","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","article-title":"What energy functions can be minimized via graph cuts?","volume":"26","author":"Kolmogorov","year":"2004","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref081","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88690-7_60","article-title":"Beyond loose LP-relaxations: Optimizing MRFs by repairing cycles","volume-title":"European Conference on Computer Vision (ECCV)","author":"Komodakis","year":"2008"},{"key":"2026032614563874200_ref082","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2007.4408890","article-title":"MRF optimization via dual decomposition: Message-passing revisited","volume-title":"International Conference on Computer Vision (ICCV)","author":"Komodakis","year":"2007"},{"key":"2026032614563874200_ref083","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Komodakis","year":"2007"},{"key":"2026032614563874200_ref084","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte","year":"2008","edition":"4th"},{"issue":"2","key":"2026032614563874200_ref085","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1109\/18.910572","article-title":"Factor graphs and the sum-product algorithm","volume":"47","author":"Kschischang","year":"2001","journal-title":"IEEE Transactions on Information Theory"},{"key":"2026032614563874200_ref086","article-title":"Structured learning with approximate inference","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Kulesza","year":"2007"},{"key":"2026032614563874200_ref087","article-title":"Discriminative fields for modeling spatial dependencies in natural images","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Kumar","year":"2004"},{"issue":"2-3","key":"2026032614563874200_ref088","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s10994-009-5111-0","article-title":"Structured prediction by joint kernel support estimation","volume":"77","author":"Lampert","year":"2009","journal-title":"Machine Learning"},{"key":"2026032614563874200_ref089","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2008.4587586","article-title":"Beyond sliding windows: Object localization by Efficient Subwindow Search","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Lampert","year":"2008"},{"issue":"12","key":"2026032614563874200_ref090","doi-asserted-by":"crossref","first-page":"2129","DOI":"10.1109\/TPAMI.2009.144","article-title":"Efficient subwindow search: A branch and bound framework for object localization","volume":"31","author":"Lampert","year":"2009","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"issue":"465","key":"2026032614563874200_ref091","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1198\/016214504000000098","article-title":"Multicategory support vector machines","volume":"99","author":"Lee","year":"2004","journal-title":"Journal of the American Statistical Association"},{"key":"2026032614563874200_ref092","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/3-540-45586-8_4","volume-title":"Computational Combinatorial Optimization","author":"Lemar\u00e9chal","year":"2001"},{"key":"2026032614563874200_ref093","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88693-8_2","article-title":"Image segmentation by branch-and-mincut","volume-title":"European Conference on Computer Vision (ECCV)","author":"Lempitsky","year":"2008"},{"key":"2026032614563874200_ref094","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2009.5459262","article-title":"Image segmentation with a bounding box prior","volume-title":"International Conference on Computer Vision (ICCV)","author":"Lempitsky","year":"2009"},{"key":"2026032614563874200_ref095","doi-asserted-by":"crossref","DOI":"10.1002\/9780470669723","volume-title":"Advanced Markov Chain Monte Carlo Methods: Learning from Past Samples","author":"Liang","year":"2010"},{"issue":"1","key":"2026032614563874200_ref096","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1007\/BF01589116","article-title":"On the limited memory BFGS method for large scale optimization","volume":"45","author":"Liu","year":"1989","journal-title":"Mathematical Programming"},{"key":"2026032614563874200_ref097","volume-title":"Monte Carlo Strategies in Scientific Computing, Springer Series in Statistics","author":"Liu","year":"2001"},{"key":"2026032614563874200_ref098","volume-title":"Information Theory, Inference and Learning Algorithms","author":"MacKay","year":"2003"},{"key":"2026032614563874200_ref099","doi-asserted-by":"crossref","DOI":"10.1145\/1553374.1553466","article-title":"Polyhedral outer approximations with application to natural language parsing","volume-title":"International Conference on Machine Learing (ICML)","author":"Martins","year":"2009"},{"key":"2026032614563874200_ref100","article-title":"Augmenting dual decomposition for MAP inference","volume-title":"Proceedings of the 3rd International Workshop on Optimization for Machine Learning (OPT 2010), December 10, 2010, Whistler, Canada","author":"Martins","year":"2010"},{"key":"2026032614563874200_ref101","volume-title":"Predicting Structured Data","author":"McAllester","year":"2007"},{"key":"2026032614563874200_ref102","article-title":"Convergent message passing algorithms\u2014a unifying view","volume-title":"Uncertainty in Artificial Intelligence (UAI)","author":"Meltzer","year":"2009"},{"issue":"6","key":"2026032614563874200_ref103","first-page":"1087","article-title":"Equation of state calculations by fast computing machines","volume":"21","author":"Metropolis","year":"1953","journal-title":"et al"},{"key":"2026032614563874200_ref104","volume-title":"Information, Physics and Computation","author":"M","year":"2009"},{"key":"2026032614563874200_ref105","article-title":"Divergence measures and message passing","volume-title":"Microsoft Research Technical Report, MSR-TR-2005-173","author":"Minka","year":"2005"},{"key":"2026032614563874200_ref106","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2007.383299","article-title":"Latent-dynamic discriminative models for continuous gesture recognition","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Morency","year":"2007"},{"key":"2026032614563874200_ref107","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2005.112","article-title":"Guiding model search using segmentation","volume-title":"International Conference on Computer Vision (ICCV)","author":"Mori","year":"2005"},{"key":"2026032614563874200_ref108","article-title":"Markov chain Monte Carlo","volume-title":"Tutorial at Machine Learning Summer School 2009","author":"Murray","year":"2009"},{"key":"2026032614563874200_ref109","first-page":"223","volume-title":"Stochastic Optimization: Algorithms and Applications","author":"Nedic","year":"2000"},{"issue":"1","key":"2026032614563874200_ref110","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","article-title":"Smooth minimization of non-smooth functions","volume":"103","author":"Nesterov","year":"2005","journal-title":"Mathematical Programming"},{"key":"2026032614563874200_ref111","volume-title":"Applied Linear Statistical Models","author":"Neter","year":"1996","edition":"4"},{"key":"2026032614563874200_ref112","doi-asserted-by":"crossref","DOI":"10.1007\/b98874","volume-title":"Numerical optimization","author":"Nocedal","year":"1999"},{"key":"2026032614563874200_ref113","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-15567-3_8","article-title":"On parameter learning in CRF-based approaches to object class image segmentation","volume-title":"European Conference on Computer Vision (ECCV)","author":"Nowozin","year":"2010"},{"key":"2026032614563874200_ref114","doi-asserted-by":"crossref","DOI":"10.1145\/1553374.1553473","article-title":"Solution stability in linear programming relaxations: graph partitioning and unsupervised learning","volume-title":"International Conference on Machine Learing (ICML)","author":"Nowozin","year":"2009"},{"key":"2026032614563874200_ref115","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2009.5206567","article-title":"Global connectivity potentials for random field models","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Nowozin","year":"2009"},{"key":"2026032614563874200_ref116","volume-title":"Combinatorial optimization: Algorithms and complexity","author":"Papadimitriou","year":"1998"},{"key":"2026032614563874200_ref117","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1007\/BFb0120902","article-title":"On the structure of all minimum cuts in a network and applications","volume-title":"Combinatorial Optimization II","author":"Picard","year":"1980"},{"key":"2026032614563874200_ref118","first-page":"185","volume-title":"Advances in Kernel Methods","author":"Platt","year":"1999"},{"key":"2026032614563874200_ref119","first-page":"61","volume-title":"Advances in Large Margin Classifiers","author":"Platt","year":"1999"},{"key":"2026032614563874200_ref120","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-15939-8_6","article-title":"Entropy and margin maximization for structured output learning","volume-title":"European Conference on Marchine Learning (ECML)","author":"Pletscher","year":"2010"},{"key":"2026032614563874200_ref121","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2007.383094","article-title":"Efficient belief propagation for vision using linear constraint nodes","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Potetz","year":"2007"},{"key":"2026032614563874200_ref122","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2008.4587401","article-title":"Exact inference in multi-label CRFs with higher order cliques","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Ramalingam","year":"2008"},{"key":"2026032614563874200_ref123","doi-asserted-by":"crossref","DOI":"10.1145\/1143844.1143936","article-title":"Maximum margin planning","volume-title":"International Conference on Machine Learing (ICML)","author":"Ratliff","year":"2006"},{"key":"2026032614563874200_ref124","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2003.1238308","article-title":"Learning a classification model for segmentation","volume-title":"International Conference on Computer Vision (ICCV)","author":"Ren","year":"2003"},{"key":"2026032614563874200_ref125","volume-title":"The Bayesian Choice. From Decision Theoretic Foundations to Computational Implementation, Springer Series in Statistics","author":"Robert","year":"2001"},{"key":"2026032614563874200_ref126","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-4145-2","volume-title":"Monte Carlo Statistical Methods","author":"Robert","year":"2004","edition":"2nd"},{"key":"2026032614563874200_ref127","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2007.383203","article-title":"Optimizing binary MRFs via extended roof duality","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Rother","year":"2007"},{"key":"2026032614563874200_ref128","doi-asserted-by":"crossref","DOI":"10.1145\/1390156.1390268","article-title":"Accurate max-margin training for structured output spaces","volume-title":"International Conference on Machine Learing (ICML)","author":"Sarawagi","year":"2008"},{"key":"2026032614563874200_ref129","first-page":"486","article-title":"Exploiting tractable substructures in intractable networks","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Saul","year":"1995"},{"key":"2026032614563874200_ref130","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Savchynskyy","year":"2011"},{"key":"2026032614563874200_ref131","first-page":"113","article-title":"Syntactic analysis of two-dimensional visual signals in noisy conditions in Russian","volume":"4","author":"Schlesinger","year":"1976","journal-title":"Kibernetika"},{"key":"2026032614563874200_ref132","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2007.4409018","article-title":"Fast matching of planar shapes in sub-cubic runtime","volume-title":"International Conference on Computer Vision (ICCV)","author":"Schmidt","year":"2007"},{"key":"2026032614563874200_ref133","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2009.5206863","article-title":"Efficient planar graph cuts with applications in computer vision","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Schmidt","year":"2009"},{"key":"2026032614563874200_ref134","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2010.5539844","article-title":"A generative perspective on MRFs in low-level vision","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Schmidt","year":"2010"},{"key":"2026032614563874200_ref135","volume-title":"Learning with Kernels","author":"Sch\u00f6lkopf","year":"2002"},{"key":"2026032614563874200_ref136","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Schraudolph","year":"2008"},{"key":"2026032614563874200_ref137","article-title":"Efficient exact inference in planar ising models","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Schraudolph","year":"2008"},{"issue":"2","key":"2026032614563874200_ref138","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1016\/0004-3702(94)90072-8","article-title":"Finding MAPs for belief networks Is NP-hard","volume":"68","author":"Shimony","year":"1994","journal-title":"Artificial Intelligence"},{"key":"2026032614563874200_ref139","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-82118-9","volume-title":"Minimization Methods for Non-differentiable Functions","author":"Shor","year":"1985"},{"key":"2026032614563874200_ref140","article-title":"Clusters and coarse partitions in LP relaxations","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Sontag","year":"2008"},{"key":"2026032614563874200_ref141","volume-title":"Optimization for Machine Learning","author":"Sontag","year":"2011"},{"key":"2026032614563874200_ref142","first-page":"503","article-title":"Tightening LP Relaxations for MAP using Message Passing","volume-title":"Uncertainty in Artificial Intelligence (UAI)","author":"Sontag","year":"2008"},{"key":"2026032614563874200_ref143","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2010.5539886","article-title":"Parallel and distributed graph cuts by dual decomposition","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Strandmark","year":"2010"},{"issue":"2\u20133","key":"2026032614563874200_ref144","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1007\/s10994-009-5112-z","article-title":"Piecewise training for structured prediction","volume":"77","author":"Sutton","year":"2009","journal-title":"Machine Learning"},{"issue":"6","key":"2026032614563874200_ref145","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1109\/TPAMI.2007.70844","article-title":"A comparative study of energy minimization methods for markov random fields with smoothness-based priors","volume":"30","author":"Szeliski","year":"2008","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref146","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88688-4_43","article-title":"Learning CRFs using graph cuts","volume-title":"European Conference on Computer Vision (ECCV)","author":"Szummer","year":"2008"},{"key":"2026032614563874200_ref147","first-page":"900","volume-title":"International Conference on Computer Vision (ICCV)","author":"Tappen","year":"2003"},{"key":"2026032614563874200_ref148","article-title":"Max-margin Markov networks","volume-title":"Conference on neural information processing systems (NIPS)","author":"Taskar","year":"2003"},{"key":"2026032614563874200_ref149","first-page":"1","article-title":"Bundle methods for regularized risk minimization","volume":"1","author":"Teo","year":"2009","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"2026032614563874200_ref150","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88688-4_44","article-title":"Feature correspondence via graph matching: Models and global optimization","volume-title":"European Conference on Computer Vision (ECCV)","author":"Torresani","year":"2008"},{"key":"2026032614563874200_ref151","first-page":"1453","article-title":"Large margin methods for structured and interdependent output variables","volume":"6","author":"Tsochantaridis","year":"2005","journal-title":"Journal of Machine Learning Research (JMLR)"},{"issue":"2","key":"2026032614563874200_ref152","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s11263-005-6642-x","article-title":"Image parsing: Unifying segmentation, detection, and recognition","volume":"63","author":"Tu","year":"2005","journal-title":"International Journal of Computer Vision (IJCV)"},{"key":"2026032614563874200_ref153","volume-title":"Journal of Signal Processing Systems","author":"Tuia","year":"2010"},{"key":"2026032614563874200_ref154","volume-title":"Theory of Pattern Recognition (in Russian)","author":"Vapnik","year":"1974"},{"key":"2026032614563874200_ref155","volume-title":"Approximation Algorithms","author":"Vazirani","year":"2001"},{"key":"2026032614563874200_ref156","article-title":"Structured output regression for detection with partial occulsion","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Vedaldi","year":"2009"},{"key":"2026032614563874200_ref157","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2008.4587440","article-title":"Graph cut based image segmentation with connectivity priors","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Vicente","year":"2008"},{"key":"2026032614563874200_ref158","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2009.5459287","article-title":"Joint optimization of segmentation and appearance models","volume-title":"International Conference on Computer Vision (ICCV)","author":"Vicente","year":"2009"},{"key":"2026032614563874200_ref159","first-page":"969","article-title":"Accelerated training of conditional random fields with stochastic gradient methods","volume-title":"International Conference on Machine Learing (ICML)","author":"Vishwanathan","year":"2006"},{"issue":"1-2","key":"2026032614563874200_ref160","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1561\/2200000001","article-title":"Graphical models, exponential families and variational inference","volume":"1","author":"Wainwright","year":"2008","journal-title":"Foundations and Trends in Machine Learning"},{"key":"2026032614563874200_ref161","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-88682-2_47","article-title":"Efficiently learning random fields for stereo vision with sparse message passing","volume-title":"European Conference on Computer Vision (ECCV)","author":"Weinman","year":"2008"},{"issue":"7","key":"2026032614563874200_ref162","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","article-title":"A linear programming approach to max-sum problem: A review","volume":"29","author":"Werner","year":"2007","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence (T-PAMI)"},{"key":"2026032614563874200_ref163","doi-asserted-by":"crossref","DOI":"10.1109\/CVPR.2008.4587355","article-title":"High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (MAP-MRF)","volume-title":"IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR)","author":"Werner","year":"2008"},{"key":"2026032614563874200_ref164","article-title":"Revisiting the decomposition approach to inference in exponential families and graphical models","volume-title":"Center for Machine Perception, Czech Technical University Prague, Research Report, CTU-CMP-2009-06","author":"Werner","year":"2009"},{"key":"2026032614563874200_ref165","article-title":"Belief propagation fixed points as zero gradients of a function of reparameterizations","volume-title":"Center for Machine Perception, Czech Technical University Prague, Research Report, CTU-CMP-2010-05","author":"Werner","year":"2010"},{"key":"2026032614563874200_ref166","volume-title":"Model Building in Mathematical Programming","author":"Williams","year":"1999","edition":"4"},{"key":"2026032614563874200_ref167","first-page":"661","article-title":"Variational message passing","volume":"6","author":"Winn","year":"2005","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"2026032614563874200_ref168","volume-title":"Integer Programming","author":"Wolsey","year":"1998"},{"key":"2026032614563874200_ref169","doi-asserted-by":"crossref","DOI":"10.1109\/ICCV.2009.5459434","article-title":"A global perspective on MAP inference for low-level vision","volume-title":"International Conference on Computer Vision (ICCV)","author":"Woodford","year":"2009"},{"key":"2026032614563874200_ref170","first-page":"583","article-title":"A generalized mean field algorithm for variational inference in exponential families","volume-title":"Uncertainty in Artificial Intelligence (UAI)","author":"Xing","year":"2003"},{"key":"2026032614563874200_ref171","article-title":"Constructing free energy approximations and generalized belief propagation algorithms","volume-title":"MERL Technical Report, 2004-040","author":"Yedidia","year":"2004"},{"key":"2026032614563874200_ref172","doi-asserted-by":"crossref","DOI":"10.1145\/1553374.1553523","article-title":"Learning structural SVMs with latent variables","volume-title":"International Conference on Machine Learing (ICML)","author":"Yu","year":"2009"},{"key":"2026032614563874200_ref173","first-page":"1593","article-title":"The convergence of contrastive divergences","volume-title":"Conference on Neural Information Processing Systems (NIPS)","author":"Yuille","year":"2005"},{"issue":"7","key":"2026032614563874200_ref174","doi-asserted-by":"crossref","first-page":"1691","DOI":"10.1162\/08997660260028674","article-title":"CCCP algorithms to minimize the Bethe and Kikuchi free energies: Convergent alternatives to belief propagation","volume":"14","author":"Yuille","year":"2002","journal-title":"Neural Computation"},{"issue":"4","key":"2026032614563874200_ref175","doi-asserted-by":"crossref","first-page":"915","DOI":"10.1162\/08997660360581958","article-title":"The concave-convex procedure","volume":"15","author":"Yuille","year":"2003","journal-title":"Neural Computation"},{"issue":"1","key":"2026032614563874200_ref176","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1214\/aos\/1079120130","article-title":"Statistical behavior and consistency of classification methods based on convex risk minimization","volume":"32","author":"Zhang","year":"2004","journal-title":"Annals of Statistics"},{"issue":"2","key":"2026032614563874200_ref177","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1007925832420","article-title":"Filters, random fields and maximum entropy (FRAME): Towards a unified theory for texture modeling","volume":"27","author":"Zhu","year":"1998","journal-title":"International Journal of Computer Vision (IJCV)"}],"container-title":["Foundations and Trends\u00ae in Computer Graphics and Vision"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.emerald.com\/ftcgv\/article-pdf\/6\/3-4\/185\/11138645\/0600000033en.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/www.emerald.com\/ftcgv\/article-pdf\/6\/3-4\/185\/11138645\/0600000033en.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,26]],"date-time":"2026-03-26T18:57:10Z","timestamp":1774551430000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.emerald.com\/ftcgv\/article\/6\/3-4\/185\/1331434\/Structured-Learning-and-Prediction-in-Computer"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,5,23]]},"references-count":177,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2011,5,23]]}},"URL":"https:\/\/doi.org\/10.1561\/0600000033","relation":{},"ISSN":["1572-2740","1572-2759"],"issn-type":[{"value":"1572-2740","type":"print"},{"value":"1572-2759","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,5,23]]}}}