{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:26:17Z","timestamp":1750220777541,"version":"3.41.0"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"National Science Foundation","award":["1447413"],"award-info":[{"award-number":["1447413"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>We describe a general framework for probabilistic modeling of complex scenes and for inference from ambiguous observations. The approach is motivated by applications in image analysis and is based on the use of priors defined by stochastic grammars. We define a class of grammars that capture relationships between the objects in a scene and provide important contextual cues for statistical inference. The distribution over scenes defined by a probabilistic scene grammar can be represented by a graphical model, and this construction can be used for efficient inference with loopy belief propagation.<\/jats:p><jats:p>We show experimental results with two applications. One application involves the reconstruction of binary contour maps. Another application involves detecting and localizing faces in images. In both applications, the same framework leads to robust inference algorithms that can effectively combine local information to reason about a scene.<\/jats:p>","DOI":"10.1145\/3396886","type":"journal-article","created":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T04:09:40Z","timestamp":1590898180000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Scene Grammars, Factor Graphs, and Belief Propagation"],"prefix":"10.1145","volume":"67","author":[{"given":"Jeroen","family":"Chua","sequence":"first","affiliation":[{"name":"Brown University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pedro F.","family":"Felzenszwalb","sequence":"additional","affiliation":[{"name":"Brown University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Alfred V. Aho Ravi Sethi and Jeffrey D. Ullman. 1986. Compilers: Principles Tools and Techniques. Addison-Wesley. Alfred V. Aho Ravi Sethi and Jeffrey D. Ullman. 1986. Compilers: Principles Tools and Techniques. Addison-Wesley."},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Yali Amit. 2002. 2D Object Detection and Recognition. MIT Press. Yali Amit. 2002. 2D Object Detection and Recognition. MIT Press.","DOI":"10.7551\/mitpress\/1006.001.0001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.161"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1986.tb01412.x"},{"key":"e_1_2_1_5_1","unstructured":"Elie Bienenstock Stuart Geman and Daniel Potter. 1997. Compositionality MDL priors and object recognition. In Advances in Neural Information Processing Systems. 838--844. Elie Bienenstock Stuart Geman and Daniel Potter. 1997. Compositionality MDL priors and object recognition. In Advances in Neural Information Processing Systems. 838--844."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0054769"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-010-0391-1"},{"key":"e_1_2_1_8_1","unstructured":"Rama Chellapa and Anil Jain. 1993. Markov Random Fields: Theory and Application. Academic Press. Rama Chellapa and Anil Jain. 1993. Markov Random Fields: Theory and Application. Academic Press."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056813"},{"key":"e_1_2_1_10_1","unstructured":"Thomas Cormen Charles Leiserson Ronald Rivest and Clifford Stein. 2001. Introduction to Algorithms (2nd ed.). The MIT Press. Thomas Cormen Charles Leiserson Ronald Rivest and Clifford Stein. 2001. Introduction to Algorithms (2nd ed.). The MIT Press."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.177"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1977.tb01600.x"},{"key":"e_1_2_1_13_1","unstructured":"Frank Drewes. 2006. Grammatical Picture Generation. Springer. Frank Drewes. 2006. Grammatical Picture Generation. Springer."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Richard Durbin Sean R. Eddy Anders Krogh and Graeme Mitchison. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press. Richard Durbin Sean R. Eddy Anders Krogh and Graeme Mitchison. 1998. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press.","DOI":"10.1017\/CBO9780511790492"},{"key":"e_1_2_1_15_1","unstructured":"M. Everingham L. Van Gool C. K. I. Williams J. Winn and A. Zisserman. 2012. The PASCAL Visual Object Classes Challenge 2012 (VOC2012) Results. M. Everingham L. Van Gool C. K. I. Williams J. Winn and A. Zisserman. 2012. The PASCAL Visual Object Classes Challenge 2012 (VOC2012) Results."},{"key":"e_1_2_1_16_1","unstructured":"Pedro F. Felzenszwalb Ross B. Girshick and David McAllester. 2010. Discriminatively Trained Deformable Part Models Release 4. Pedro F. Felzenszwalb Ross B. Girshick and David McAllester. 2010. Discriminatively Trained Deformable Part Models Release 4."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2009.167"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:VISI.0000042934.15159.49"},{"key":"e_1_2_1_19_1","unstructured":"Pedro F. Felzenszwalb and David McAllester. 2010. Object detection grammars. Univerity of Chicago Computer Science Technical Report 2010-02 (2010). Pedro F. Felzenszwalb and David McAllester. 2010. Object detection grammars. Univerity of Chicago Computer Science Technical Report 2010-02 (2010)."},{"key":"e_1_2_1_20_1","unstructured":"Pedro F. Felzenszwalb and John G. Oberlin. 2014. Multiscale fields of patterns. In Advances in Neural Information Processing Systems. 82--90. Pedro F. Felzenszwalb and John G. Oberlin. 2014. Multiscale fields of patterns. In Advances in Neural Information Processing Systems. 82--90."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1973.223602"},{"key":"e_1_2_1_22_1","unstructured":"King Sun Fu. 1974. Syntactic Methods in Pattern Recognition. Elsevier. King Sun Fu. 1974. Syntactic Methods in Pattern Recognition. Elsevier."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.476006"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767596"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/1939008"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Ulf Grenander. 1993. General Pattern Theory. Oxford University Press. Ulf Grenander. 1993. General Pattern Theory. Oxford University Press.","DOI":"10.1093\/oso\/9780198536710.001.0001"},{"key":"e_1_2_1_27_1","unstructured":"Matthew T. Harrison. 2005. Discovering Compositional Structures. Ph.D. Dissertation. Brown University. Matthew T. Harrison. 2005. Discovering Compositional Structures. Ph.D. Dissertation. Brown University."},{"key":"e_1_2_1_28_1","unstructured":"Tom Heskes Onno Zoeter and Wim Wiegerinck. 2004. Approximate expectation maximization. In Advances in Neural Information Processing Systems 16. 353--360. Tom Heskes Onno Zoeter and Wim Wiegerinck. 2004. Approximate expectation maximization. In Advances in Neural Information Processing Systems 16. 353--360."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition","volume":"2","author":"Jin Ya","year":"2006"},{"key":"e_1_2_1_31_1","unstructured":"Dan Klein. 2005. The Unsupervised Learning of Natural Language Structure. Ph.D. Dissertation. Stanford University. Dan Klein. 2005. The Unsupervised Learning of Natural Language Structure. Ph.D. Dissertation. Stanford University."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2015.7299068"},{"key":"e_1_2_1_34_1","unstructured":"Christopher D. Manning and Hinrich Sch\u00fctze. 1999. Foundations of Statistical Natural Language Processing. MIT Press. Christopher D. Manning and Hinrich Sch\u00fctze. 1999. Foundations of Statistical Natural Language Processing. MIT Press."},{"key":"e_1_2_1_35_1","unstructured":"David Mumford. 1994. The Bayesian rationale for energy functionals. Geometry-driven Diffusion in Computer Vision Haar Romeny (Ed.). Springer 141--153. David Mumford. 1994. The Bayesian rationale for energy functionals. Geometry-driven Diffusion in Computer Vision Haar Romeny (Ed.). Springer 141--153."},{"volume-title":"Algebraic Geometry and Its Applications","author":"Mumford David","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","unstructured":"Kevin P. Murphy Yair Weiss and Michael I. Jordan. 1999. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artificial Intelligence. 467--475. Kevin P. Murphy Yair Weiss and Michael I. Jordan. 1999. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artificial Intelligence. 467--475."},{"volume-title":"Vision Science: Photons to Phenomenology","year":"1999","author":"Palmer Stephen E.","key":"e_1_2_1_38_1"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Judea Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann. Judea Pearl. 1988. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann.","DOI":"10.1016\/B978-0-08-051489-5.50008-4"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Przemyslaw Prusinkiewicz and Aristid Lindenmayer. 1991. The Algorithmic Beauty of Plants (The Virtual Laboratory). Springer. Przemyslaw Prusinkiewicz and Aristid Lindenmayer. 1991. The Algorithmic Beauty of Plants (The Virtual Laboratory). Springer.","DOI":"10.1007\/978-1-4613-8476-2"},{"key":"e_1_2_1_41_1","unstructured":"Azriel Rosenfeld. 1979. Picture Languages (Formal Models for Picture Recognition). Academic Press. Azriel Rosenfeld. 1979. Picture Languages (Formal Models for Picture Recognition). Academic Press."},{"key":"e_1_2_1_42_1","unstructured":"A. Shashua and S. Ullman. 1988. Structural saliency: The detection of globally salient structures using a locally connected network. MIT AI Lab Memo No. 1061 (1988). A. Shashua and S. Ullman. 1988. Structural saliency: The detection of globally salient structures using a locally connected network. MIT AI Lab Memo No. 1061 (1988)."},{"key":"e_1_2_1_43_1","unstructured":"Andreas Stolcke. 1994. Bayesian Learning of Probabilistic Language Models. Ph.D. Dissertation. University of California at Berkeley. Andreas Stolcke. 1994. Bayesian Learning of Probabilistic Language Models. Ph.D. Dissertation. University of California at Berkeley."},{"key":"e_1_2_1_44_1","unstructured":"Daniel Tarlow Kevin Swersky Richard S. Zemel Ryan Prescott Adams and Brendan J. Frey. 2012. Fast exact inference for recursive cardinality models. In Uncertainty in Artificial Intelligence. Daniel Tarlow Kevin Swersky Richard S. Zemel Ryan Prescott Adams and Brendan J. Frey. 2012. Fast exact inference for recursive cardinality models. In Uncertainty in Artificial Intelligence."},{"volume-title":"Proceedings of the International Conference on Learning Representations.","author":"Tran Dustin","key":"e_1_2_1_45_1"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-005-6642-x"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976600300015880"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1162\/neco.1997.9.4.837"},{"key":"e_1_2_1_50_1","unstructured":"Jonathan S. Yedidia William T. Freeman and Yair Weiss. 2001. Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium. Morgan Kaufmann 236--239. Jonathan S. Yedidia William T. Freeman and Yair Weiss. 2001. Understanding belief propagation and its generalizations. In Exploring Artificial Intelligence in the New Millennium. Morgan Kaufmann 236--239."},{"key":"e_1_2_1_51_1","unstructured":"Yibiao Zhao and Song-Chun Zhu. 2011. Image parsing with stochastic scene grammar. In Advances in Neural Information Processing Systems. 73--81. Yibiao Zhao and Song-Chun Zhu. 2011. Image parsing with stochastic scene grammar. In Advances in Neural Information Processing Systems. 73--81."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2008.67"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1561\/0600000018"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396886","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3396886","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:23Z","timestamp":1750200083000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396886"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,30]]},"references-count":52,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3396886"],"URL":"https:\/\/doi.org\/10.1145\/3396886","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2020,5,30]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}