A generalized random walk with restart and its application in depth up-sampling and interactive segmentation

Bumsub Ham, Dongbo Min, Kwanghoon Sohn

Research output: Contribution to journalArticlepeer-review

26 Scopus citations


In this paper, the origin of random walk with restart (RWR) and its generalization are described. It is well known that the random walk (RW) and the anisotropic diffusion models share the same energy functional, i.e., the former provides a steady-state solution and the latter gives a flow solution. In contrast, the theoretical background of the RWR scheme is different from that of the diffusion-reaction equation, although the restarting term of the RWR plays a role similar to the reaction term of the diffusion-reaction equation. The behaviors of the two approaches with respect to outliers reveal that they possess different attributes in terms of data propagation. This observation leads to the derivation of a new energy functional, where both volumetric heat capacity and thermal conductivity are considered together, and provides a common framework that unifies both the RW and the RWR approaches, in addition to other regularization methods. The proposed framework allows the RWR to be generalized (GRWR) in semilocal and nonlocal forms. The experimental results demonstrate the superiority of GRWR over existing regularization approaches in terms of depth map up-sampling and interactive image segmentation.

Original languageEnglish
Article number6482622
Pages (from-to)2574-2588
Number of pages15
JournalIEEE Transactions on Image Processing
Issue number7
StatePublished - 2013


  • Anisotropic diffusion
  • depth up-sampling
  • diffusion-reaction equation
  • interactive segmentation
  • random walk with restart (RWR)
  • thermal diffusivity


Dive into the research topics of 'A generalized random walk with restart and its application in depth up-sampling and interactive segmentation'. Together they form a unique fingerprint.

Cite this