AF: Small: Counting and Sampling Cuts and Paths in Planar and Lattice Graphs

该奖项的目标是在几个受限图类（包括平面图、8连通的2D网格和3D网格）中对许多切割和路径问题的计数和采样变体。这些图类主要是由计算机视觉中的应用程序驱动的，其中最近的几个结果重新引起了对这些问题的最小化变体的兴趣。相应的计数和抽样变量的重要性，除其他外，源于底层概率模型（如马尔可夫随机场）参数的自动学习。提出的研究建立在PI最近的工作上，即计数和采样最小（s,t）切割和最小单源多汇切割与连接先验，两者都在平面图上。这些问题用于图像分割应用，并形成了计算加权切割的配分函数的最终目标的第一步，即所有(s,t)-切割的切割权值之和；这个量对于通过极大似然原理学习模型参数是必不可少的。PI将研究各种各样的切割和路径问题，从不同的角度概括初始结果。这些包括研究其他连接先验，超越平面性，超越最小切割和最短路径。本研究将积极吸引本科生和硕士生参与。相关的教育材料预计每年将影响600多名学生，其中约10名来自国家聋人技术学院。除了会议和期刊等标准的传播场所外，PI还将在每年的Imagine RIT节上展示结果。2012年，这个社区拓展节吸引了大约3.5万名游客，其中许多是中学生和高中生。

This award targets counting and sampling variants of a number of cut and path problems in several restricted graph classes including planar graphs, the 8-connected 2D grid, and the 3D grid. These graph classes are primarily motivated by applications in computer vision where several recent results renewed interest in the minimization variants of these problems. The importance of the corresponding counting and sampling variants stems from, among others, automated learning of the parameters of the underlying probabilistic models such as the Markov Random Field.The proposed research builds on the PI's recent works on counting and sampling minimum (s,t)-cuts and minimum single-source-multi-sink cuts with connectivity priors, both in planar graphs. These problems are used in image segmentation applications and form an initial step towards the ultimate goal of computing the partition function for weighted cuts, i.e., the summation of the cut weights across all (s,t)-cuts; this quantity is essential for model parameter learning via the maximum likelihood principle. The PI will study a variety of cut and path problems that generalize the initial results from different perspectives. These include studying other connectivity priors, moving beyond planarity, and beyond minimum cuts and shortest paths.The research will actively involve undergraduate and master students. Related educational materials are projected to annually impact over 600 students, about 10 of them from the National Technical Institute for the Deaf. In addition to standard dissemination venues like conferences and journals, the PI will also present the results at the annual Imagine RIT festival. This community outreach festival attracted about 35,000 visitors in 2012, many of them middle and high school students.