论文标题
使用半混凝土方案进行分类和图像处理，以供忠诚度强迫Allen- cahn在图表上
Classification and image processing with a semi-discrete scheme for fidelity forced Allen--Cahn on graphs
论文作者
论文摘要
本文介绍了Allen-Cahn方程（ACE）的半混凝土隐式EULER（SDIE）方案，并在图表上强迫。 Bertozzi and Flenner（2012）率先使用了这种微分方程作为图形分类问题的方法，例如半监督学习和图像分割。在Merkurjev，Kostić和Bertozzi（2013）中，使用了一种具有忠实强迫的Merriman-Bence-Osher（MBO）方案，因为MBO方案与ACE具有启发性相似。本文严格地建立了以Fidelity强迫为特殊情况的SDIE方案的特殊情况。这种连接需要在ACE中使用双凸电势，如Budd和Van Gennip（2020）中所示的ACE无忠诚。我们还证明，随着SDIE时间步长趋向于零，SDIE方案的解决方案会以坚决强迫收敛到图ACE的解决方案。 接下来，我们将SDIE方案作为分类算法开发。我们还向SDIE和MBO计划的算法介绍了一些创新。对于大图，我们使用QR分解方法来计算NyStröm扩展的特征分类，该分量的表现优于例如Bertozzi和Flenner（2012）的准确性，稳定性和速度。此外，我们通过基于矩阵指数的strang公式的计算来代替方案扩散步骤的Euler离散化。我们将此算法应用于许多图像分割问题，并比较SDIE和MBO方案的性能。我们发现，尽管一般的SDIE方案在此任务中的表现并不比MBO的特殊情况好，但我们的其他创新导致比以前文献的细分明显更好。我们还从经验上量化了这种分割从尼斯特罗姆扩展中的随机性继承的不确定性。
This paper introduces a semi-discrete implicit Euler (SDIE) scheme for the Allen-Cahn equation (ACE) with fidelity forcing on graphs. Bertozzi and Flenner (2012) pioneered the use of this differential equation as a method for graph classification problems, such as semi-supervised learning and image segmentation. In Merkurjev, Kostić, and Bertozzi (2013), a Merriman-Bence-Osher (MBO) scheme with fidelity forcing was used instead, as the MBO scheme is heuristically similar to the ACE. This paper rigorously establishes the graph MBO scheme with fidelity forcing as a special case of an SDIE scheme for the graph ACE with fidelity forcing. This connection requires using the double-obstacle potential in the ACE, as was shown in Budd and Van Gennip (2020) for ACE without fidelity forcing. We also prove that solutions of the SDIE scheme converge to solutions of the graph ACE with fidelity forcing as the SDIE time step tends to zero. Next, we develop the SDIE scheme as a classification algorithm. We also introduce some innovations into the algorithms for the SDIE and MBO schemes. For large graphs, we use a QR decomposition method to compute an eigendecomposition from a Nyström extension, which outperforms the method used in e.g. Bertozzi and Flenner (2012) in accuracy, stability, and speed. Moreover, we replace the Euler discretisation for the scheme's diffusion step by a computation based on the Strang formula for matrix exponentials. We apply this algorithm to a number of image segmentation problems, and compare the performance of the SDIE and MBO schemes. We find that whilst the general SDIE scheme does not perform better than the MBO special case at this task, our other innovations lead to a significantly better segmentation than that from previous literature. We also empirically quantify the uncertainty that this segmentation inherits from the randomness in the Nyström extension.
