# Overview

Many problems in image processing and analysis can be interpreted as labeling problems, which aim to find the optimal mapping from a set of sites to a set of labels. A site represents a certain primitive, such as a pixel, while a label represents a certain quantity, such as disparity in stereo correspondence. Considering this labeling interpretation, instead of solving different problems individually, a series of unified frameworks for labeling problems are introduced here.

# Generalized Random Walks

In this Generalized Random Walks (GRW) model [3][4], we formulate a labeling problem from Markov chain random walk point of view, where probabilities are considered as transition probabilities of a random walker moving between nodes: When an image and labels are represented as a weighted graph, where a node/site can be either a pixel or a label, the weight associated with an edge (after normalization by the degree of an incident node) represents the probability that a random walker transits from one incident node/site to the other incident node/site in a single move. To emphasize similarity, as well as differences, to Markov random field model, we refer to the functions defining the edge weights as *compatibility functions*. This formulation allows compatibility functions to be defined in any form according to the need of a particular problem. In addition, it allows the inclusion of label nodes and pre-labeled scene nodes to be represented naturally in the current framework without altering the structure of the graph, i.e., the whole graph can still be represneted as a single Laplacian. GRW was applied to image fusion and stereo matching.

# Multivariate Gaussian Conditional Random Field

In this Multivariate Gaussian Conditional Random Field (MGCRF) model [1][4], we show that GRW is a special case of the proposed MGCRF when the boundary condition is defined in a specific form and the precision matrix is an identity matrix. MGCRF considers random vectors (rather than random variables) defined on each node in a graph.

# Hierarchical Random Walks and Hierarchical Multivariate Gaussian Conditional Random Field

These two models are hierarchical versions of GRW and MGCRF, respectively [1][4]. The basic idea is to accelerate the computation by constructing a hierarchy of fine-to-coarse graphs and using the result from a coarser graph to initiate the calculation on a finer graph.

# Multiscale Random Walks

This is a multiscale version of GRW [2][4]. The objective is also to accelerate the computation. However, different from hierarchical random walks (HRW), multiscale random walks (MRW) constructs a fine-to-coarse hierarchy of the input data instead of a hierarchy of the graph. MRW was applied to form a cross-scale fusion rule for image fusion that can significantly enhance fusion quality even with simple multiscale decomposition methods.

# Related Publications

[1]. **Rui Shen**, Irene Cheng, and Anup Basu. **QoE-Based Multi-Exposure Fusion in Hierarchical Multivariate Gaussian CRF**. *IEEE Transactions on Image Processing*, vol. 22, no. 6, pages 2469-2478, 2013. [MGCRF and HMGCRF and their application][Image Fusion Page]

[2]. **Rui Shen**, Irene Cheng, and Anup Basu. **Cross-Scale Coefficient Selection for Volumetric Medical Image Fusion**. *IEEE Transactions on BioMedical Engineering*, vol. 60, no. 4, pages 1069-1079, 2013. [MRW and its application][Image Fusion Page]

[3]. **Rui Shen**, Irene Cheng, Jianbo Shi, and Anup Basu. **Generalized Random Walks for Fusion of Multi-Exposure Images**. *IEEE Transactions on Image Processing*, vol. 20, no. 12, pages 3634-3646, 2011. [GRW and its application][Image Fusion Page][TIP11 Page]

[4]. **Rui Shen**. **Probabilistic Methods for Discrete Labeling Problems in Digital Image Processing and Analysis**. PhD Thesis, University of Alberta, 2012. [GRW, HRW, MRW, MGCRF, HMGCRF, and their applications][Image Fusion Page]