A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> Image annotation plays an important role in image retrieval and management. However, the results of the state-of-the-art image annotation methods are often unsatisfactory. Therefore, it is necessary to refine the imprecise annotations obtained by existing annotation methods. In this paper, a novel approach to automatically refine the original annotations of images is proposed. On the one hand, for Web images, textual information, e.g. file name and surrounding text, is used to retrieve a set of candidate annotations. On the other hand, for non-Web images that are lack of textual information, a relevance model-based algorithm using visual information is used to decide the candidate annotations. Then, candidate annotations are re-ranked and only the top ones are reserved as the final annotations. To re-rank the annotations, an algorithm using Random Walk with Restarts (RWR) is proposed to leverage both the corpus information and the original confidence information of the annotations. Experimental results on both non-Web images of Corel dataset and Web images of photo forum sites demonstrate the effectiveness of the proposed method. <s> BIB001 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> We consider the problem of multi-label, supervised image segmentation when an initial labeling of some pixels is given. In this paper, we propose a new generative image segmentation algorithm for reliable multi-label segmentations in natural images. In contrast to most existing algorithms which focus on the inter-label discrimination, we address the problem of finding the generative model for each label. The primary advantage of our algorithm is that it produces very good segmentation results under two difficult problems: the weak boundary problem and the texture problem. Moreover, single-label image segmentation is possible. These are achieved by designing the generative model with the Random Walks with Restart (RWR). Experimental results with synthetic and natural images demonstrate the relevance and accuracy of our algorithm. <s> BIB002 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> In this paper, we consider the colorization problem of grayscale images in which some color scribbles are initially given. Our proposed method is based on the weighted color blending of the scribbles. Unlike previous works which utilize the shortest distance as the blending weights, we employ a new intrinsic distance measure based on the Random Walks with Restart (RWR), known as a very successful technique for defining the relevance between two nodes in a graph. In our work, we devise new modified data-driven RWR framework that can incorporate locally adaptive and data-driven restarting probabilities. In this new framework, the restarting probability of each pixel becomes dependent on its edgeness, generated by the canny detector. Since this data-driven RWR enforces color consistency in the areas bounded by the edges, it produces more reliable edge-preserving colorization results that are less sensitive to the size and position of each scribble. Moreover, if the additional information about the scribbles which indicate the foreground object is available, our method can be readily applied to the object segmentation and matting. Experiments on several synthetic, cartoon and natural images demonstrate that our method achieves much high quality colorization results compared with the state-of-the-art methods. <s> BIB003 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> This paper presents a probabilistic method for correspondence matching with a framework of the random walk with restart (RWR). The matching cost is reformulated as a corresponding probability, which enables the RWR to be utilized for matching the correspondences. There are mainly two advantages in our method. First, the proposed method guarantees the non-trivial steady-state solution of a given initial matching probability due to the restarting term in the RWR. It means the number of iteration, a crucial parameter which influences the performance of algorithm, is not needed in contrast to the conventional methods. This gives the consistent results regardless of the evolution time. Second, only an adjacent neighborhood is considered when the matching probabilities are inferred, which lowers the computational complexity while not sacrificing performance. Experimental results show that the performance of the proposed method is competitive to that of state-of-the-art methods both qualitatively and quantitatively. <s> BIB004 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> 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. <s> BIB005 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> In this paper, we propose a graph-based multiscale saliency-detection algorithm by modeling eye movements as a random walk on a graph. The proposed algorithm first extracts intensity, color, and compactness features from an input image. It then constructs a fully connected graph by employing image blocks as the nodes. It assigns a high edge weight if the two connected nodes have dissimilar intensity and color features and if the ending node is more compact than the starting node. Then, the proposed algorithm computes the stationary distribution of the Markov chain on the graph as the saliency map. However, the performance of the saliency detection depends on the relative block size in an image. To provide a more reliable saliency map, we develop a coarse-to-fine refinement technique for multiscale saliency maps based on the random walk with restart (RWR). Specifically, we use the saliency map at a coarse scale as the restarting distribution of RWR at a fine scale. Experimental results demonstrate that the proposed algorithm detects visual saliency precisely and reliably. Moreover, the proposed algorithm can be efficiently used in the applications of proto-object extraction and image retargeting. <s> BIB006 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> A novel saliency detection algorithm for video sequences based on the random walk with restart (RWR) is proposed in this paper. We adopt RWR to detect spatially and temporally salient regions. More specifically, we first find a temporal saliency distribution using the features of motion distinctiveness, temporal consistency, and abrupt change. Among them, the motion distinctiveness is derived by comparing the motion profiles of image patches. Then, we employ the temporal saliency distribution as a restarting distribution of the random walker. In addition, we design the transition probability matrix for the walker using the spatial features of intensity, color, and compactness. Finally, we estimate the spatiotemporal saliency distribution by finding the steady-state distribution of the walker. The proposed algorithm detects foreground salient objects faithfully, while suppressing cluttered backgrounds effectively, by incorporating the spatial transition matrix and the temporal restarting distribution systematically. Experimental results on various video sequences demonstrate that the proposed algorithm outperforms conventional saliency detection algorithms qualitatively and quantitatively. <s> BIB007 </s> A Survey on Personalized PageRank Computation Algorithms <s> D. COMPUTER VISION <s> In this paper, we propose a robust dense stereo reconstruction algorithm using a random walk with restart. The pixel-wise matching costs are aggregated into superpixels and the modified random walk with restart algorithm updates the matching cost for all possible disparities between the superpixels. In comparison to the majority of existing stereo methods using the graph cut, belief propagation, or semi-global matching, our proposed method computes the final reconstruction through the determination of the best disparity at each pixel in the matching cost update. In addition, our method also considers occlusion and depth discontinuities through the visibility and fidelity terms. These terms assist in the cost update procedure in the calculation of the standard smoothness constraint. The method results in minimal computational costs while achieving high accuracy in the reconstruction. We test our method on standard benchmark datasets and challenging real-world sequences. We also show that the processing time increases linearly in relation to an increase in the disparity search range. We develop a robust stereo matching algorithm using a random walk with restart.The proposed method considers occlusion and depth discontinuities.The method achieves high accuracy with low computational costs in the reconstruction.Our method works well on the varying illumination and exposure test. <s> BIB008
Computer vision is one of the fields where PPR has also been widely applied. Kim et al. BIB002 addressed a multilabel supervised image segmentation problem when initial labels of some pixels are given. They introduced the generative model for image segmentation using the steady-state probability of RWR. Since RWR considers all relevance relations between the nodes in a graph (image), it is effective at addressing the texture problem. Ham et al. BIB005 proposed a generalized random walk with restart (GRWR), which is a generalized version of RWR that adopts local and nonlocal approaches for image regularization. They applied GRWR to depth map upsampling and interactive image segmentation and showed that the GRWR is more robust to outliers and can aggregate texture information better. Wang et al. BIB001 utilized PPR to refine image annotations. After a relevance model-based algorithm determines the candidate annotations, RWR is used to rerank the annotations based on the corpus information and original confidence. Kim et al. BIB006 proposed a multiscale saliency detection algorithm that uses RWR to refine a saliency map. Similarly, Kim et al. BIB007 proposed a spatiotemporal saliency detection algorithm for video sequences based on RWR. Lee et al. BIB008 proposed a robust dense stereo reconstruction algorithm using RWR. Kim et al. BIB003 devised a modified data-driven RWR framework that can incorporate locally adaptive and data-driven restarting probabilities to handle the colorization problem of grayscale images. Oh et al. BIB004 presented a probabilistic method for correspondence matching using RWR.