Submodular Field Grammars: Representation, Inference, and Application to Image Parsing
Natural scenes contain many layers of part-subpart structure, and distributions over them are thus naturally represented by stochastic image grammars, with one production per decomposition of a part. Unfortunately, in contrast to language grammars, where the number of possible split points for a production A → BC is linear in the length of A, in an image there are an exponential number of ways to split a region into subregions. This makes parsing intractable and requires image grammars to be severely restricted in practice, for example by allowing only rectangular regions. In this paper, we address this problem by associating with each production a submodular Markov random field whose labels are the subparts and whose labeling segments the current object into these subparts. We call the resulting model a submodular field grammar (SFG). Finding the MAP split of a region into subregions is now tractable, and by exploiting this we develop an efficient approximate algorithm for MAP parsing of images with SFGs. Empirically, we show promising improvements in accuracy when using SFGs for scene understanding, and demonstrate exponential improvements in inference time compared to traditional methods, while returning comparable minima.
I thank the authors for their response.  I felt the authors gave an good response to my questions.  I encourage the authors to more carefully clarify the task since it is a non-standard task if the paper is accepted. ----------- Original review ---------- Summary: Similar to text parsing based on formal grammars, this paper proposes a way to parse images based on formal visual grammars that have a part, subpart structure such as Scene -> Sky, Ground.  The key problem is that splitting the image into *arbitrarily-shaped* pixel regions to associate with the production rules is computationally difficult in general.  This paper proposes to associate formal grammar production rules with submodular Markov random fields (MRF).  The submodular structure of the associated MRF allows for fast inference for a single rule into arbitrarily-shaped subregions and a dynamic-programming-like algorithm for parsing the entire image structure.  The experimental results show that the method is indeed much faster than previous methods.  Pros: 1) Well-written and easy to read even though some of the details are fairly technical. 2) Excellent speed results with competitive or better accuracy. 3) Novel combination of MRFs and formal grammars for images  Cons: 1) The specific task (i.e. input data/parameters and output) seemed a little confusing (note that I am not particularly familiar with the parsing task especially for images).  Is the task a hierarchical version of semantic segmentation?  Are the raw image pixels given to the algorithm or just semantic features like segmentation label?  In one place the energy seems to depend on the raw pixels (Sec. 2.1) but later the energy is denoted to only depend on y (Sec. 4.1); maybe this is just a notation thing but I wanted to check. 2) The experiments are also a little confusing but maybe this is just because the task is not a classic task.  How are the DeepLab unary features used?  Are they used instead of the raw pixel values? 3) What would be an example of a non-tree-structured grammar (see lines 66-68)?  It would be good to more clearly describe the difference from [6,7 ref in paper] that are similar but for tree-structured grammars.  Minor comments: The illustrations were very helpful in making the ideas concrete.  I would suggest presenting the theorem/propositions first and then giving comments on them instead of defining them after giving comments.