This paper addresses the problem of video object segmentation, where the
initial object mask is given in the first frame of an input video. We propose a
novel spatio-temporal Markov Random Field (MRF) model defined over pixels to
handle this problem. Unlike conventional MRF models, the spatial dependencies
among pixels in our model are encoded by a Convolutional Neural Network (CNN).
Specifically, for a given object, the probability of a labeling to a set of
spatially neighboring pixels can be predicted by a CNN trained for this
specific object. As a result, higher-order, richer dependencies among pixels in
the set can be implicitly modeled by the CNN. With temporal dependencies
established by optical flow, the resulting MRF model combines both spatial and
temporal cues for tackling video object segmentation. However, performing
inference in the MRF model is very difficult due to the very high-order
dependencies. To this end, we propose a novel CNN-embedded algorithm to perform
approximate inference in the MRF. This algorithm proceeds by alternating
between a temporal fusion step and a feed-forward CNN step. When initialized
with an appearance-based one-shot segmentation CNN, our model outperforms the
winning entries of the DAVIS 2017 Challenge, without resorting to model
ensembling or any dedicated detectors.

该论文介绍了一种解决视频对象分割问题的新型空间 - 时间马尔可夫随机场（MRF）模型，该模型通过卷积神经网络（CNN）编码像素之间的空间依赖关系，并利用光流建立时间依赖关系来结合空间和时间线索，提出了一种嵌入 CNN 的算法，以实现近似的 MRF 推理。

基于 CNN 的高阶时空 MRF 推理的视频目标分割

CNN in MRF: Video Object Segmentation via Inference in A CNN-Based  Higher-Order Spatio-Temporal MRF

We propose a deterministic algorithm for approximately counting the number of
list colorings of a graph. Under the assumption that the graph is triangle
free, the size of every list is at least $\alpha \Delta$, where $\alpha$ is an
arbitrary constant bigger than $\alpha^{**}=2.8432...$, and $\Delta$ is the
maximum degree of the graph, we obtain the following results. For the case when
the size of the each list is a large constant, we show the existence of a
\emph{deterministic} FPTAS for computing the total number of list colorings.
The same deterministic algorithm has complexity $2^{O(\log^2 n)}$, without any
assumptions on the sizes of the lists, where $n$ is the instance size. We
further extend our method to a discrete Markov random field (MRF) model. Under
certain assumptions relating the size of the alphabet, the degree of the graph
and the interacting potentials we again construct a deterministic FPTAS for
computing the partition function of a MRF.
Our results are not based on the most powerful existing counting technique --
rapidly mixing Markov chain method. Rather we build upon concepts from
statistical physics, in particular, the decay of correlation phenomena and its
implication for the uniqueness of Gibbs measures in infinite graphs. This
approach was proposed in two recent papers \cite{BandyopadhyayGamarnikCounting}
and \cite{weitzCounting}. The principle insight of this approach is that the
correlation decay property can be established with respect to certain
\emph{computation tree}, as opposed to the conventional correlation decay
property with respect to graph theoretic neighborhoods of a given node. This
allows truncation of computation at a logarithmic depth in order to obtain
polynomial accuracy in polynomial time.

提出了一种确定性算法，用于大致计算图的列表着色数量及离散马尔可夫随机场模型的分区函数，该算法基于统计物理学中的相关性衰减现象，并且不需要最强的计数技术。