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.