Qiu Huaijun John, Hancock Edwin R
Queen Mary Vision Laboratory, Department of Computer Science, Queen Mary, University of London, London, UK E1 4NS.
IEEE Trans Pattern Anal Mach Intell. 2007 Nov;29(11):1873-90. doi: 10.1109/TPAMI.2007.1103.
This paper exploits the properties of the commute time between nodes of a graph for the purposes of clustering and embedding, and explores its applications to image segmentation and multi-body motion tracking. Our starting point is the lazy random walk on the graph, which is determined by the heatkernel of the graph and can be computed from the spectrum of the graph Laplacian. We characterize the random walk using the commute time (i.e. the expected time taken for a random walk to travel between two nodes and return) and show how this quantity may be computed from the Laplacian spectrum using the discrete Green's function. Our motivation is that the commute time can be anticipated to be a more robust measure of the proximity of data than the raw proximity matrix. In this paper, we explore two applications of the commute time. The first is to develop a method for image segmentation using the eigenvector corresponding to the smallest eigenvalue of the commute time matrix. We show that our commute time segmentation method has the property of enhancing the intra-group coherence while weakening inter-group coherence and is superior to the normalized cut. The second application is to develop a robust multi-body motion tracking method using an embedding based on the commute time. Our embedding procedure preserves commute time, and is closely akin to kernel PCA, the Laplacian eigenmap and the diffusion map. We illustrate the results both on synthetic image sequences and real world video sequences, and compare our results with several alternative methods.
本文利用图中节点间通勤时间的性质进行聚类和嵌入，并探索其在图像分割和多体运动跟踪中的应用。我们的出发点是图上的懒惰随机游走，它由图的热核决定，并且可以从图拉普拉斯算子的谱中计算得出。我们使用通勤时间（即随机游走在两个节点之间往返所需的预期时间）来刻画随机游走，并展示如何使用离散格林函数从拉普拉斯谱计算这个量。我们的动机是，与原始的邻近矩阵相比，通勤时间有望成为衡量数据邻近程度的更稳健的指标。在本文中，我们探索了通勤时间的两种应用。第一种是使用通勤时间矩阵最小特征值对应的特征向量开发一种图像分割方法。我们表明，我们的通勤时间分割方法具有增强组内一致性同时减弱组间一致性的性质，并且优于归一化割。第二种应用是使用基于通勤时间的嵌入开发一种稳健的多体运动跟踪方法。我们的嵌入过程保留了通勤时间，并且与核主成分分析、拉普拉斯特征映射和扩散映射密切相关。我们在合成图像序列和真实世界视频序列上展示了结果，并将我们的结果与几种替代方法进行了比较。
