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年，这个社区外联节吸引了大约35 000名游客，其中许多是初中和高中学生。

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.